Cycle Detection and Bipartite Checking

Interviewer cue: “can all tasks finish given these dependencies”, “is there a deadlock”, or “can you split these people/items into two groups with no conflicts” — all three boil down to the same two questions on a graph: does a cycle exist, and is this graph 2-colorable? Both questions reuse the traversal templates from Phase 5, with one extra piece of bookkeeping each.

What you’ll learn

Cycle detection in an undirected graph — DFS that tracks each node’s parent, and the equivalent Union-Find approach.
Cycle detection in a directed graph — the 3-color (white/gray/black) DFS, and why a plain visited set isn’t enough.
Bipartite checking — 2-coloring the graph with BFS so every edge connects opposite colors.
Why undirected and directed graphs need genuinely different cycle checks.

Undirected graphs: DFS with a parent pointer

In an undirected graph, every edge (u, v)(u, v) is stored both ways — so a plain DFS immediately “revisits” the node it just came from. That’s not a cycle; it’s just walking back over the same edge. The fix: skip only the edge back to your immediate parent, but treat reaching any other already-visited node as a real cycle.

cycle_undirected_dfs.py

def has_cycle_undirected(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    visited = set()
 
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True   # reached a visited node that ISN'T my parent -> cycle
        return False
 
    return any(node not in visited and dfs(node, -1) for node in range(n))
 
 
tree_edges = [(0, 1), (1, 2), (1, 3)]              # a tree: no cycle
cyclic_edges = [(0, 1), (1, 2), (2, 0), (1, 3)]     # 0-1-2-0 forms a triangle
 
print("tree has cycle:", has_cycle_undirected(4, tree_edges))
print("graph has cycle:", has_cycle_undirected(4, cyclic_edges))

cycle_undirected_dfs.py

def has_cycle_undirected(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    visited = set()
 
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True   # reached a visited node that ISN'T my parent -> cycle
        return False
 
    return any(node not in visited and dfs(node, -1) for node in range(n))
 
 
tree_edges = [(0, 1), (1, 2), (1, 3)]              # a tree: no cycle
cyclic_edges = [(0, 1), (1, 2), (2, 0), (1, 3)]     # 0-1-2-0 forms a triangle
 
print("tree has cycle:", has_cycle_undirected(4, tree_edges))
print("graph has cycle:", has_cycle_undirected(4, cyclic_edges))

diagram A cycle exists once DFS reaches an already-visited, non-parent node mermaid

  graph TD
    N0["0"] --- N1["1"]
    N1 --- N2["2"]
    N2 --- N0
    N1 --- N3["3"]

DFS from 00 goes 0 -> 1 -> 20 -> 1 -> 2. From 22, the edge back to 11 is skipped (that’s the parent), but the edge 2 -> 02 -> 0 lands on 00, which is visited and is not 22’s parent — that’s the back edge that proves the triangle 0-1-20-1-2 is a cycle.

Undirected graphs: the Union-Find alternative

Union-Find answers the same question without recursion: process edges one at a time, and if both endpoints are already in the same set before you union them, that edge closes a cycle.

cycle_undirected_union_find.py

def has_cycle_union_find(n, edges):
    parent = list(range(n))
 
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
 
    for u, v in edges:
        root_u, root_v = find(u), find(v)
        if root_u == root_v:
            return True          # u and v were already connected -> this edge is a cycle
        parent[root_u] = root_v
 
    return False
 
 
tree_edges = [(0, 1), (1, 2), (1, 3)]
cyclic_edges = [(0, 1), (1, 2), (2, 0), (1, 3)]
 
print("tree has cycle:", has_cycle_union_find(4, tree_edges))
print("graph has cycle:", has_cycle_union_find(4, cyclic_edges))

cycle_undirected_union_find.py

def has_cycle_union_find(n, edges):
    parent = list(range(n))
 
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
 
    for u, v in edges:
        root_u, root_v = find(u), find(v)
        if root_u == root_v:
            return True          # u and v were already connected -> this edge is a cycle
        parent[root_u] = root_v
 
    return False
 
 
tree_edges = [(0, 1), (1, 2), (1, 3)]
cyclic_edges = [(0, 1), (1, 2), (2, 0), (1, 3)]
 
print("tree has cycle:", has_cycle_union_find(4, tree_edges))
print("graph has cycle:", has_cycle_union_find(4, cyclic_edges))

Directed graphs: the 3-color DFS

A directed graph needs a different check entirely — there’s no “parent edge” to skip, and a plain visited set gives false positives on graphs where two branches simply share a descendant without ever looping. The fix is three states per node: white (untouched), gray (on the current DFS path), black (fully explored and safe forever). A cycle exists exactly when an edge points at a graygray node.

cycle_directed_dfs.py

WHITE, GRAY, BLACK = 0, 1, 2
 
 
def has_cycle_directed(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
 
    state = [WHITE] * n
 
    def dfs(node):
        state[node] = GRAY                     # on the current path
        for neighbor in graph[node]:
            if state[neighbor] == GRAY:
                return True                     # back edge to the current path -> cycle
            if state[neighbor] == WHITE and dfs(neighbor):
                return True
        state[node] = BLACK                     # fully explored, never re-check
        return False
 
    return any(state[i] == WHITE and dfs(i) for i in range(n))
 
 
dag_edges = [(0, 1), (0, 2), (1, 3), (2, 3)]     # a DAG: 3 has two parents, no cycle
cyclic_edges = [(0, 1), (1, 2), (2, 0)]           # 0 -> 1 -> 2 -> 0
 
print("DAG has cycle:", has_cycle_directed(4, dag_edges))
print("directed graph has cycle:", has_cycle_directed(3, cyclic_edges))

cycle_directed_dfs.py

WHITE, GRAY, BLACK = 0, 1, 2
 
 
def has_cycle_directed(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
 
    state = [WHITE] * n
 
    def dfs(node):
        state[node] = GRAY                     # on the current path
        for neighbor in graph[node]:
            if state[neighbor] == GRAY:
                return True                     # back edge to the current path -> cycle
            if state[neighbor] == WHITE and dfs(neighbor):
                return True
        state[node] = BLACK                     # fully explored, never re-check
        return False
 
    return any(state[i] == WHITE and dfs(i) for i in range(n))
 
 
dag_edges = [(0, 1), (0, 2), (1, 3), (2, 3)]     # a DAG: 3 has two parents, no cycle
cyclic_edges = [(0, 1), (1, 2), (2, 0)]           # 0 -> 1 -> 2 -> 0
 
print("DAG has cycle:", has_cycle_directed(4, dag_edges))
print("directed graph has cycle:", has_cycle_directed(3, cyclic_edges))

Bipartite checking: 2-coloring with BFS

A graph is bipartite if you can split its nodes into two groups such that every edge connects one group to the other — equivalently, if you can color every node with one of two colors so no edge joins two same-colored nodes. BFS makes this a one-line rule: color every unvisited neighbor the opposite color of the current node, and fail the moment two same-color nodes share an edge.

is_bipartite.py

from collections import deque
 
 
def is_bipartite(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    color = {}
    for start in range(n):
        if start in color:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]   # flip the color
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False                         # same color on both ends of an edge
 
    return True
 
 
square_edges = [(0, 1), (1, 2), (2, 3), (3, 0)]          # even cycle -- 2-colorable
triangle_edges = [(0, 1), (1, 2), (2, 0)]                 # odd cycle -- NOT 2-colorable
 
print("4-cycle is bipartite:", is_bipartite(4, square_edges))
print("3-cycle (triangle) is bipartite:", is_bipartite(3, triangle_edges))

is_bipartite.py

from collections import deque
 
 
def is_bipartite(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    color = {}
    for start in range(n):
        if start in color:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]   # flip the color
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False                         # same color on both ends of an edge
 
    return True
 
 
square_edges = [(0, 1), (1, 2), (2, 3), (3, 0)]          # even cycle -- 2-colorable
triangle_edges = [(0, 1), (1, 2), (2, 0)]                 # odd cycle -- NOT 2-colorable
 
print("4-cycle is bipartite:", is_bipartite(4, square_edges))
print("3-cycle (triangle) is bipartite:", is_bipartite(3, triangle_edges))

diagram 2-coloring a 4-cycle: opposite colors on every edge mermaid

  graph LR
    N0["0 (color A)"] --- N1["1 (color B)"]
    N1 --- N2["2 (color A)"]
    N2 --- N3["3 (color B)"]
    N3 --- N0

Every edge above joins a “color A” node to a “color B” node — that’s what makes the 4-cycle bipartite. A triangle can never be 2-colored: going around it flips the color three times, so the third node ends up matching the color of the first, forcing a same-color edge.

Complexity

All three checks are a single BFS/DFS pass: $O(V + E)$ time. Space is $O(V)$ for the visited set / color map / parent array (plus recursion depth for the DFS versions).

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 785 — Is Graph Bipartite? · Medium

Problem. Given an undirected graph as an adjacency list, return TrueTrue if it is bipartite — its nodes can be split into two sets with every edge joining the two sets.

Constraints. 1 <= n <= 1001 <= n <= 100, no self-loops or parallel edges. The graph may be disconnected.

Examples. [[1,2,3],[0,2],[0,1,3],[0,2]][[1,2,3],[0,2],[0,1,3],[0,2]] gives FalseFalse · [[1,3],[0,2],[1,3],[0,2]][[1,3],[0,2],[1,3],[0,2]] gives TrueTrue

Editorial

Bipartite is equivalent to 2-colourable, and a graph is 2-colourable exactly when it contains no odd-length cycle. Traversing and assigning alternating colours tests that directly: a conflict means you have closed a cycle of odd length.

Time $O(V + E)$ . Space $O(V)$ .

Two details:

The outer loop over every node. The graph may be disconnected, so a single traversal from node 0 can miss components entirely. The if start in colour: continueif start in colour: continue guard skips already-coloured components.
1 - colour[node]1 - colour[node] flips between 0 and 1 without a conditional.

The first example is FalseFalse because nodes 0, 1 and 2 form a triangle — an odd cycle. [[], []][[], []] is two isolated nodes, trivially bipartite.

Either DFS or BFS works; there is no distance question. Union-find can also solve it by unioning each node with its neighbours’ “opposite” proxies, but colouring is more direct.

Follow-ups: “Return the two sets?” — collect nodes by colour. “Why odd cycles?” — walking an odd cycle forces two adjacent nodes to share a colour; be ready to say it. “Three colours?” — 3-colourability is NP-complete, a sharp and worth-knowing contrast. “Directed graph?” — bipartiteness ignores direction, so treat it as undirected.

LC 886 — Possible Bipartition · Medium

Problem. Given nn people and a list of mutual dislikes, return TrueTrue if everyone can be split into two groups such that no two people who dislike each other share a group.

Constraints. 1 <= n <= 20001 <= n <= 2000, 0 <= len(dislikes) <= 10^40 <= len(dislikes) <= 10^4, people are labelled 1..n1..n.

Examples. n = 4, dislikes = [[1,2],[1,3],[2,4]]n = 4, dislikes = [[1,2],[1,3],[2,4]] gives TrueTrue · n = 3, dislikes = [[1,2],[1,3],[2,3]]n = 3, dislikes = [[1,2],[1,3],[2,3]] gives FalseFalse

Editorial

The modelling step is the content: “split people into two groups so that no disliking pair shares a group” is graph bipartiteness, with people as nodes and dislikes as edges.

Time $O(V + E)$ . Space $O(V + E)$ .

Once modelled, the code is LC 785 verbatim plus adjacency-list construction. Two small differences worth noting:

1-indexed labels, so the outer loop is range(1, n + 1)range(1, n + 1). Using range(n)range(n) silently skips person nn and examines a nonexistent person 00.
Edge list input, so you must build the adjacency both ways — dislike is mutual.

(3, [[1,2],[1,3],[2,3]])(3, [[1,2],[1,3],[2,3]]) is a triangle: three mutually disliking people cannot be split into two groups. That is the odd-cycle obstruction.

Follow-ups: “Three groups?” — 3-colouring, NP-complete. “Return the groups?” — read them off the colour map. “What if some pairs must be together?” — that adds equality constraints, making it a union-find problem alongside the colouring, similar to LC 990. “Maximise the split when it is impossible?” — max-cut, NP-hard.

LC 1361 — Validate Binary Tree Nodes · Medium

Problem. Given nn nodes numbered 0..n-10..n-1 with leftChild[i]leftChild[i] and rightChild[i]rightChild[i] (or -1-1), return TrueTrue if they form exactly one valid binary tree.

Constraints. 1 <= n <= 10^41 <= n <= 10^4, child values are -1-1 or valid node indices.

Examples. n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] gives TrueTrue · with rightChild = [2,3,-1,-1]rightChild = [2,3,-1,-1] gives FalseFalse (node 3 has two parents) · n = 2, leftChild = [1,0], rightChild = [-1,-1]n = 2, leftChild = [1,0], rightChild = [-1,-1] gives FalseFalse (a cycle)

Editorial

Three conditions, and all three are necessary:

No node has two parents — in-degree at most 1.
Exactly one node has in-degree 0 — the root.
Every node is reachable from that root.

Time $O(n)$ . Space $O(n)$ .

The interesting part is why (3) cannot be dropped. Consider two nodes forming a cycle pointing at each other, alongside a separate valid tree: every node in the cycle has in-degree exactly 1, so condition (1) holds, and the tree contributes exactly one in-degree-0 node, so (2) holds too. Yet the structure is not a single tree. (2, [1,0], [-1,-1])(2, [1,0], [-1,-1]) is the minimal version — nodes 0 and 1 point at each other, no node has in-degree 0, so it fails at (2); but larger constructions pass both degree checks and only reachability catches them.

That is the general lesson: degree conditions constrain local structure, traversal confirms global structure. Both are needed.

(1, [-1], [-1])(1, [-1], [-1]) is the single-node tree: in-degree 0, one root, reachable, TrueTrue.

Follow-ups: “Why is the reachability check needed?” — the disconnected-cycle argument; the expected question. “Union-find instead?” — union each parent with its children and reject a union that fails (a cycle) or leaves more than one component. “Validate a general tree?” — the same three conditions with unbounded children. “Detect which nodes are unreachable?” — set(range(n)) - seenset(range(n)) - seen.

LeetCode problem set

#	Problem	Difficulty	The twist
207	Course Schedule	Medium	Directed cycle detection via the 3-color DFS above; courses can finish iff there’s no cycle
—	Detect Cycle in a Directed Graph (classic)	—	The same 3-color template, phrased directly
684	Redundant Connection	Medium	Undirected cycle detection with Union-Find; return the edge that first closes the loop
785	Is Graph Bipartite?	Medium	The 2-coloring BFS above, applied directly
886	Possible Bipartition	Medium	Build a graph from the “dislikes” pairs, then run the same bipartite check

Recap

Undirected cycle: DFS with a parentparent pointer (skip only the parent edge), or Union-Find (a cycle closes the moment two endpoints share a root).
Directed cycle: 3-color DFS — a back edge to a GRAYGRAY node (on the current path) is a cycle; a BLACKBLACK node (finished via another branch) is not.
Bipartite: 2-color with BFS, flipping color across every edge; fails the instant two same-colored nodes share an edge. Equivalently: bipartite iff no odd-length cycle exists.
All three are $O(V + E)$ time, $O(V)$ space — the same traversal budget as plain BFS/DFS, just with extra per-node bookkeeping.

Next: Strongly Connected Components and Bridges — what happens when “connected” gets stricter (both directions) or the graph itself has single points of failure.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Cycle Detection and Bipartite Checking

What you’ll learn

Undirected graphs: DFS with a parent pointer

Undirected graphs: the Union-Find alternative

Directed graphs: the 3-color DFS

Bipartite checking: 2-coloring with BFS

Complexity

Practice — real LeetCode problems

LC 785 — Is Graph Bipartite? · Medium

LC 886 — Possible Bipartition · Medium

LC 1361 — Validate Binary Tree Nodes · Medium

LeetCode problem set

Recap

Was this page helpful?