SyntaxPilot
Courses/DSA and Coding Problems/Lesson 50
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 50 of 90

Cycle detection in undirected and directed graphs

queued

These are the notes for DSA episode 50. Does a graph contain a cycle, a walk that comes back to where it started? The question sounds the same for cables (undirected edges) and for formulas that need other cells (directed edges), but the two need different tricks. We start from two real-life loops, define every word, then for undirected graphs try a brute force (unplug each edge and check) that hits Time Limit Exceeded, find the insight (a second road to a vertex we've already seen), watch the naive version give a wrong answer on a plain line, and fix it with the parent check. For directed graphs, the parent check gives a wrong answer on a diamond; the fix is DFS with three colours, where a cycle is an arrow to a grey vertex. A recursive DFS crashes with a real StackOverflowError on a 1 lakh chain, so we finish with an iterative DFS using our own stack. Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

An office network. Computers are joined by cables, and a cable works both ways. If someone plugs in one extra cable and makes a loop, a broadcast message can circle that loop forever and flood the network (network engineers call it a broadcast storm). Is there a loop?

A spreadsheet. Cell A1's formula uses B1, and B1's formula uses C1. A formula points one way: from the cell to the cell it needs. If C1 then uses A1, no cell can be calculated first, and the spreadsheet shows a circular reference warning.

Real life In code
A computer / a spreadsheet cell a vertex
A cable (both ways) an undirected edge {a, b}
"A1 uses B1" (one way) a directed edge A1 → B1
A loop of cables an undirected cycle
A circular reference a directed cycle
A network with no loop a tree (if it is connected) / a forest

Every word, from zero

  • Graph, vertex, edge, adjacency list: from episode 47. adj.get(v) lists the neighbours of v.
  • Undirected edge {a, b}: can be walked both ways. We store it twice: b in a's list and a in b's list.
  • Directed edge a → b: one way only. Stored once, in a's list.
  • Path: a walk from vertex to vertex along edges.
  • Cycle: a path that comes back to its start without using any edge twice. In a directed graph the walk must follow the arrows.
  • Self-loop: an edge from a vertex to itself, 0 → 0. It is a cycle of length 1.
  • Tree: a connected undirected graph with no cycle. A tree on n vertices has exactly n - 1 edges; one more edge always makes a cycle.
  • Parent (in a BFS/DFS): the vertex that discovered v first.
  • DFS (depth-first search): follow one path as deep as possible, then step back and try the next branch.
  • Colours white / grey / black (0 / 1 / 2): white = not visited; grey = entered and still on the current DFS path; black = all its arrows explored.
  • Call stack, StackOverflowError: every method call that hasn't returned yet waits on the call stack; too many nested calls and Java throws StackOverflowError.
  • Diamond: 0 → 1, 0 → 2, 1 → 3, 2 → 3: two roads to 3, but no cycle.

Problem statement

Given n vertices numbered 0 to n - 1 and a list of edges, return true if the graph has a cycle.

Graph Kind Cycle?
{0,1}, {1,2} (a line) undirected false
{0,1}, {1,2}, {2,0} (a triangle) undirected true
{0,1}, and a triangle 2-3-4 (two pieces) undirected true
one vertex, no edges undirected false
0→1, 0→2, 1→3, 2→3 (diamond) directed false
0→1, 1→2, 2→0 directed true
0→3, 3→1, 1→2, 2→3 (the loop doesn't include 0) directed true
0→0 (self-loop) directed true

Sizes: up to 1 lakh vertices and edges.

All programs use this helper:

    static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (!directed) adj.get(e[1]).add(e[0]);
        }
        return adj;
    }

Part 1: undirected graphs

Brute force: unplug each cable

Unplug cable {a, b}. If a can still reach b (one BFS), there is another road from a to b, and together with the cable that is a loop. Try every cable.

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (!directed) adj.get(e[1]).add(e[0]);
        }
        return adj;
    }
    static boolean hasCycle(int n, int[][] edges) {
        for (int i = 0; i < edges.length; i++) {
            int[][] rest = new int[edges.length - 1][];
            for (int j = 0, k = 0; j < edges.length; j++) if (j != i) rest[k++] = edges[j];
            if (reaches(build(n, rest, false), edges[i][0], edges[i][1])) return true;
        }
        return false;
    }
    static boolean reaches(List<List<Integer>> adj, int s, int t) {
        boolean[] seen = new boolean[adj.size()];
        Deque<Integer> q = new ArrayDeque<>();
        seen[s] = true; q.add(s);
        while (!q.isEmpty()) {
            int v = q.poll();
            if (v == t) return true;
            for (int w : adj.get(v)) if (!seen[w]) { seen[w] = true; q.add(w); }
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}}));
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}));
        System.out.println(hasCycle(5, new int[][]{{0, 1}, {2, 3}, {3, 4}, {4, 2}}));
    }
}
false
true
true

Correct. Now a chain of 1 lakh computers, each cabled to the next (no loop):

        int n = 100000;
        int[][] line = new int[n - 1][];
        for (int i = 0; i + 1 < n; i++) line[i] = new int[]{i, i + 1};
        long t0 = System.nanoTime();
        boolean c = hasCycle(n, line);
        System.out.println(c + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
(no output: Time Limit Exceeded after 8 seconds)

Why it is slow: for each of the E edges we rebuild the graph and run a whole BFS: O(E × (V + E)), about 1 lakh × 2 lakh = 2,000 crore steps. We explore the same graph again and again.

The insight: a second road to a seen vertex

One BFS reaches every vertex for the first time by exactly one road (those first roads form a tree). If we then find an edge to a vertex we've already seen, that is a second road to it, and two different roads to the same place make a loop.

The naive version: "seen = cycle" (wrong)

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (!directed) adj.get(e[1]).add(e[0]);
        }
        return adj;
    }
    static boolean hasCycle(int n, int[][] edges) {
        List<List<Integer>> adj = build(n, edges, false);
        boolean[] seen = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            seen[s] = true; q.add(s);
            while (!q.isEmpty()) {
                int v = q.poll();
                for (int w : adj.get(v)) {
                    if (seen[w]) return true;
                    seen[w] = true; q.add(w);
                }
            }
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}}));
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}));
        System.out.println(hasCycle(5, new int[][]{{0, 1}, {2, 3}, {3, 4}, {4, 2}}));
    }
}
true
true
true

true for the plain line 0-1-2: wrong. From 0, BFS sees 1. Then, looking out from 1, its list contains 0 again, because a cable works both ways. 0 is seen, so the code shouts "cycle". But that is the same cable walked backwards, not a second road.

The fix: skip the parent

Remember who discovered each vertex (its parent). From v, a seen neighbour counts as a cycle only if it is not v's parent.

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (!directed) adj.get(e[1]).add(e[0]);
        }
        return adj;
    }
    static boolean hasCycle(int n, int[][] edges) {
        List<List<Integer>> adj = build(n, edges, false);
        boolean[] seen = new boolean[n];
        int[] parent = new int[n];
        Deque<Integer> q = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            seen[s] = true; parent[s] = -1; q.add(s);
            while (!q.isEmpty()) {
                int v = q.poll();
                for (int w : adj.get(v)) {
                    if (!seen[w]) { seen[w] = true; parent[w] = v; q.add(w); }
                    else if (w != parent[v]) return true;
                }
            }
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}}));
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}));
        System.out.println(hasCycle(5, new int[][]{{0, 1}, {2, 3}, {3, 4}, {4, 2}}));
        System.out.println(hasCycle(1, new int[][]{}));
    }
}
false
true
true
false

And the 1 lakh chain that timed out:

false, 46 ms

Parallel edges (two cables between the same two computers) are a loop too. This BFS finds them from the parent's side: looking out from 0, the second copy of 1 is already seen and is not 0's parent. A recursive DFS that skips "the parent vertex" can miss them; the safe rule is to skip the parent edge (by its index), not every edge to the parent vertex.

Part 2: directed graphs

The parent trick fails

Same BFS with the parent check, but on directed edges:

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (!directed) adj.get(e[1]).add(e[0]);
        }
        return adj;
    }
    static boolean hasCycle(int n, int[][] edges) {
        List<List<Integer>> adj = build(n, edges, true);
        boolean[] seen = new boolean[n];
        int[] parent = new int[n];
        Deque<Integer> q = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            seen[s] = true; parent[s] = -1; q.add(s);
            while (!q.isEmpty()) {
                int v = q.poll();
                for (int w : adj.get(v)) {
                    if (!seen[w]) { seen[w] = true; parent[w] = v; q.add(w); }
                    else if (w != parent[v]) return true;
                }
            }
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println(hasCycle(4, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}}));
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}));
    }
}
true
true

true for the diamond: wrong. Vertex 3 is reached twice, through 1 and through 2. With cables that would be a loop, but with arrows there is no way back from 3. In a directed graph, two roads to the same vertex are not a cycle. A cycle needs an arrow back to a vertex we are still walking from.

The insight: three colours

Use DFS and paint every vertex:

Colour Number Meaning
white 0 not visited yet
grey 1 entered, still on the current DFS path
black 2 finished: all its arrows explored, no cycle below it

The rule for an arrow v → w:

  • w is grey: w is still on our current path, so we walked in a circle back to it. Cycle.
  • w is black: fully explored earlier, nothing below it loops. Skip it (this is the diamond's 3).
  • w is white: go into it.

Walkthrough on 0 → 1, 1 → 2, 1 → 3, 3 → 0: DFS enters 0 (grey), 1 (grey), 2 (grey). 2 has no arrows: black, step back. 1 → 3: grey. 3 → 0: 0 is grey, still on the path 0, 1, 3. Cycle 0 → 1 → 3 → 0.

Recursive DFS with colours

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (!directed) adj.get(e[1]).add(e[0]);
        }
        return adj;
    }
    static boolean hasCycle(int n, int[][] edges) {
        List<List<Integer>> adj = build(n, edges, true);
        int[] color = new int[n];
        for (int s = 0; s < n; s++)
            if (color[s] == 0 && dfs(adj, s, color)) return true;
        return false;
    }
    static boolean dfs(List<List<Integer>> adj, int v, int[] color) {
        color[v] = 1;
        for (int w : adj.get(v)) {
            if (color[w] == 1) return true;
            if (color[w] == 0 && dfs(adj, w, color)) return true;
        }
        color[v] = 2;
        return false;
    }
    public static void main(String[] args) {
        System.out.println(hasCycle(4, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}}));
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}));
        System.out.println(hasCycle(4, new int[][]{{0, 3}, {3, 1}, {1, 2}, {2, 3}}));
        System.out.println(hasCycle(1, new int[][]{{0, 0}}));
    }
}
false
true
true
true

Diamond false, triangle true, the loop 3 → 1 → 2 → 3 that doesn't include the start true, self-loop true.

Now a 1 lakh chain of arrows 0 → 1 → 2 → ... → 99999:

Exception in thread "main" java.lang.StackOverflowError
    at Main.dfs(Main.java:22)
    at Main.dfs(Main.java:24)
    ...

A lakh nested calls to dfs, and the call stack ran out.

The optimal solution in Java: iterative DFS with our own stack

Our own stack holds the current path, which is exactly the grey vertices. A recursive call remembers where it was in its for loop; we remember it in next[v]: the index of the next arrow of v to try.

  1. Look at the top v. If it has an arrow left, take it (next[v]++): grey → cycle; white → paint grey and push.
  2. If it has no arrows left: paint it black and pop. Its parent, now on top, continues from its own next.
import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (!directed) adj.get(e[1]).add(e[0]);
        }
        return adj;
    }
    static boolean hasCycle(int n, int[][] edges) {
        List<List<Integer>> adj = build(n, edges, true);
        int[] color = new int[n], next = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (color[s] != 0) continue;
            color[s] = 1; st.push(s);
            while (!st.isEmpty()) {
                int v = st.peek();
                if (next[v] < adj.get(v).size()) {
                    int w = adj.get(v).get(next[v]++);
                    if (color[w] == 1) return true;
                    if (color[w] == 0) { color[w] = 1; st.push(w); }
                } else { color[v] = 2; st.pop(); }
            }
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println(hasCycle(4, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}}));
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}));
        System.out.println(hasCycle(4, new int[][]{{0, 3}, {3, 1}, {1, 2}, {2, 3}}));
        System.out.println(hasCycle(1, new int[][]{{0, 0}}));
    }
}
false
true
true
true

The 1 lakh chain:

false, 98 ms

The same solutions in C++

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> build(int n, const vector<pair<int, int>>& edges, bool directed) {
    vector<vector<int>> adj(n);
    for (auto [a, b] : edges) { adj[a].push_back(b); if (!directed) adj[b].push_back(a); }
    return adj;
}

// Undirected: one BFS per piece; a seen neighbour that is not our parent = a second road = a cycle.
bool hasCycleUndirected(int n, const vector<pair<int, int>>& edges) {
    auto adj = build(n, edges, false);
    vector<bool> seen(n, false);
    vector<int> parent(n, -1);
    for (int s = 0; s < n; s++) {
        if (seen[s]) continue;
        queue<int> q; seen[s] = true; q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int w : adj[v]) {
                if (!seen[w]) { seen[w] = true; parent[w] = v; q.push(w); }
                else if (w != parent[v]) return true;
            }
        }
    }
    return false;
}

// Directed: iterative DFS with three colours (0 white, 1 grey, 2 black); an arrow to grey = a cycle.
bool hasCycleDirected(int n, const vector<pair<int, int>>& edges) {
    auto adj = build(n, edges, true);
    vector<int> color(n, 0), nxt(n, 0);
    for (int s = 0; s < n; s++) {
        if (color[s] != 0) continue;
        stack<int> st; color[s] = 1; st.push(s);
        while (!st.empty()) {
            int v = st.top();
            if (nxt[v] < (int)adj[v].size()) {
                int w = adj[v][nxt[v]++];
                if (color[w] == 1) return true;
                if (color[w] == 0) { color[w] = 1; st.push(w); }
            } else { color[v] = 2; st.pop(); }
        }
    }
    return false;
}

int main() {
    cout << boolalpha;
    cout << hasCycleUndirected(3, {{0, 1}, {1, 2}}) << "\n";                    // false
    cout << hasCycleUndirected(3, {{0, 1}, {1, 2}, {2, 0}}) << "\n";            // true
    cout << hasCycleDirected(4, {{0, 1}, {0, 2}, {1, 3}, {2, 3}}) << "\n";      // false (diamond)
    cout << hasCycleDirected(4, {{0, 3}, {3, 1}, {1, 2}, {2, 3}}) << "\n";      // true
    cout << hasCycleDirected(1, {{0, 0}}) << "\n";                              // true (self-loop)
}
false
true
false
true
true

The same solutions in Python

from collections import deque

def build(n, edges, directed):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        if not directed:
            adj[b].append(a)
    return adj

def has_cycle_undirected(n, edges):
    adj = build(n, edges, False)
    seen, parent = [False] * n, [-1] * n
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        q = deque([s])
        while q:
            v = q.popleft()
            for w in adj[v]:
                if not seen[w]:
                    seen[w], parent[w] = True, v
                    q.append(w)
                elif w != parent[v]:
                    return True
    return False

def has_cycle_directed(n, edges):
    adj = build(n, edges, True)
    color, nxt = [0] * n, [0] * n          # 0 white, 1 grey, 2 black
    for s in range(n):
        if color[s]:
            continue
        color[s] = 1
        st = [s]
        while st:
            v = st[-1]
            if nxt[v] < len(adj[v]):
                w = adj[v][nxt[v]]
                nxt[v] += 1
                if color[w] == 1:
                    return True
                if color[w] == 0:
                    color[w] = 1
                    st.append(w)
            else:
                color[v] = 2
                st.pop()
    return False

print(has_cycle_undirected(3, [(0, 1), (1, 2)]))                  # False
print(has_cycle_undirected(3, [(0, 1), (1, 2), (2, 0)]))          # True
print(has_cycle_directed(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))    # False (diamond)
print(has_cycle_directed(4, [(0, 3), (3, 1), (1, 2), (2, 3)]))    # True
print(has_cycle_directed(1, [(0, 0)]))                            # True (self-loop)
False
True
False
True
True

Python's default recursion limit is 1,000 calls, so the iterative version matters even more there.

Two real bugs

Bug 1: never painting a vertex black

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (!directed) adj.get(e[1]).add(e[0]);
        }
        return adj;
    }
    static boolean hasCycle(int n, int[][] edges) {
        List<List<Integer>> adj = build(n, edges, true);
        int[] color = new int[n];
        for (int s = 0; s < n; s++)
            if (color[s] == 0 && dfs(adj, s, color)) return true;
        return false;
    }
    static boolean dfs(List<List<Integer>> adj, int v, int[] color) {
        color[v] = 1;
        for (int w : adj.get(v)) {
            if (color[w] == 1) return true;
            if (color[w] == 0 && dfs(adj, w, color)) return true;
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println(hasCycle(4, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}}));
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}));
    }
}
true
true

true for the diamond. 3 stayed grey after it was finished, so reaching it again through 2 looked like walking back onto the current path. Finished vertices must turn black.

Bug 2: the directed colours on an undirected graph

import java.util.*;

public class Main {
    static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            if (!directed) adj.get(e[1]).add(e[0]);
        }
        return adj;
    }
    static boolean hasCycle(int n, int[][] edges) {
        List<List<Integer>> adj = build(n, edges, false);
        int[] color = new int[n];
        for (int s = 0; s < n; s++)
            if (color[s] == 0 && dfs(adj, s, color)) return true;
        return false;
    }
    static boolean dfs(List<List<Integer>> adj, int v, int[] color) {
        color[v] = 1;
        for (int w : adj.get(v)) {
            if (color[w] == 1) return true;
            if (color[w] == 0 && dfs(adj, w, color)) return true;
        }
        color[v] = 2;
        return false;
    }
    public static void main(String[] args) {
        System.out.println(hasCycle(3, new int[][]{{0, 1}, {1, 2}}));
    }
}
true

true for a plain line. 0 is grey, the DFS goes to 1, and 1's list contains 0 again because the cable works both ways. 0 is grey, so: "cycle". Each algorithm for its own kind of graph: for cables use the parent check (or union-find, practice 1).

Complexity

Approach Graph Time Space 1 lakh chain
Unplug each edge + BFS undirected O(E × (V + E)) O(V + E) Time Limit Exceeded
BFS + parent undirected O(V + E) O(V + E) milliseconds
Union-find (practice 1) undirected O(E × α(V)) ≈ O(E) O(V) fast (not run here)
Recursive DFS, 3 colours directed O(V + E) O(V + E) StackOverflowError
Iterative DFS, 3 colours directed O(V + E) O(V + E) milliseconds
Kahn's algorithm (episode 51) directed O(V + E) O(V + E) milliseconds (episode 51)

Every vertex is entered once and every edge is looked at once (twice for an undirected edge, once from each end).

Common mistakes

Mistake What you see (real) Why Fix
Undirected: "seen = cycle" true for a line walked back over the same cable skip the parent
Directed: BFS + parent true for a diamond two roads ≠ a loop three colours
Never painting black true for a diamond finished vertices stay grey color[v] = 2 at the end
Colours on an undirected graph true for a line the cable back looks grey parent check for cables
Recursive DFS, 1 lakh deep StackOverflowError too many nested calls our own stack + next[]
Starting only from vertex 0 misses a cycle in another piece the graph may be in several pieces loop over every start vertex

Mini project: a spreadsheet circular-reference checker

Each cell lists the cells its formula uses. An arrow goes from a cell to every cell it needs; a directed cycle is a circular reference. The checker reports the arrow that closes the loop.

import java.util.*;

public class Main {
    // Mini project: a spreadsheet circular-reference checker. Each cell lists the cells its formula uses.
    // An arrow goes from a cell to every cell it needs; a directed cycle = a circular reference.
    public static void main(String[] args) {
        Map<String, List<String>> uses = new LinkedHashMap<>();
        uses.put("A1", List.of("B1", "B2"));
        uses.put("B1", List.of("C1"));
        uses.put("B2", List.of());
        uses.put("C1", List.of("D1"));
        uses.put("D1", List.of("B1"));     // D1 uses B1: B1 -> C1 -> D1 -> B1
        Map<String, Integer> color = new HashMap<>();
        for (String c : uses.keySet()) color.put(c, 0);
        for (String start : uses.keySet()) {
            if (color.get(start) != 0) continue;
            Deque<String> st = new ArrayDeque<>();
            Map<String, Integer> next = new HashMap<>();
            color.put(start, 1); st.push(start);
            while (!st.isEmpty()) {
                String v = st.peek();
                int i = next.getOrDefault(v, 0);
                List<String> out = uses.get(v);
                if (i < out.size()) {
                    next.put(v, i + 1);
                    String w = out.get(i);
                    if (color.get(w) == 1) { System.out.println("Circular reference: " + v + " uses " + w + " (still being calculated)"); return; }
                    if (color.get(w) == 0) { color.put(w, 1); st.push(w); }
                } else { color.put(v, 2); st.pop(); System.out.println("can calculate " + v); }
            }
        }
        System.out.println("No circular references");
    }
}
Circular reference: D1 uses B1 (still being calculated)

Practice

1. Redundant Connection (LeetCode 684). A tree on vertices 1..n plus one extra edge. Return the edge that closes the loop (the last such edge in the input).

Solution

Union-find (disjoint set union): keep groups of connected vertices, each with a leader. For each edge, if both ends already have the same leader they were connected, so this edge makes a cycle. Otherwise join the groups.

import java.util.*;

public class Main {
    // Redundant Connection (LeetCode 684): a tree plus one extra edge; return the edge that closes the loop.
    // Disjoint Set Union (union-find): find(x) gives the leader of x's group.
    static int[] parent;
    static int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }   // path halving
        return x;
    }
    static int[] findRedundantConnection(int[][] edges) {
        parent = new int[edges.length + 1];
        for (int i = 0; i < parent.length; i++) parent[i] = i;
        for (int[] e : edges) {
            int a = find(e[0]), b = find(e[1]);
            if (a == b) return e;          // already connected: this edge makes a cycle
            parent[a] = b;                 // join the two groups
        }
        return new int[0];
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findRedundantConnection(new int[][]{{1, 2}, {1, 3}, {2, 3}})));
        System.out.println(Arrays.toString(findRedundantConnection(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}})));
    }
}
[2, 3]
[1, 4]

2. Find Eventual Safe States (LeetCode 802). A vertex is safe if every path from it ends at a vertex with no arrows (it can never walk into a cycle). Return all safe vertices in order.

Solution

Run the three-colour DFS from every vertex. A vertex that ends black finished without finding a cycle below it, so it is safe; a vertex left grey is on or leads to a cycle.

import java.util.*;

public class Main {
    // Find Eventual Safe States (LeetCode 802): a vertex is safe if every path from it ends (never enters a cycle).
    // Three colours: after the DFS, exactly the BLACK vertices are safe.
    static int[] color;
    static boolean dfs(int[][] g, int v) {          // true = v reaches a cycle
        color[v] = 1;
        for (int w : g[v]) {
            if (color[w] == 1) return true;
            if (color[w] == 0 && dfs(g, w)) return true;
        }
        color[v] = 2;
        return false;
    }
    static List<Integer> eventualSafeNodes(int[][] g) {
        color = new int[g.length];
        List<Integer> safe = new ArrayList<>();
        for (int v = 0; v < g.length; v++) {
            if (color[v] == 0) dfs(g, v);
            if (color[v] == 2) safe.add(v);
        }
        return safe;
    }
    public static void main(String[] args) {
        System.out.println(eventualSafeNodes(new int[][]{{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}}));
    }
}
[2, 4, 5, 6]

3. Graph Valid Tree. Given n vertices and undirected edges, are they a tree?

Solution

A tree is connected with no cycle, which is the same as: exactly n - 1 edges and connected.

import java.util.*;

public class Main {
    // Graph Valid Tree: n vertices, undirected edges. A tree = connected AND no cycle,
    // which is the same as: exactly n - 1 edges AND connected.
    static boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        boolean[] seen = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>(List.of(0));
        seen[0] = true; int count = 1;
        while (!q.isEmpty())
            for (int w : adj.get(q.poll()))
                if (!seen[w]) { seen[w] = true; count++; q.add(w); }
        return count == n;
    }
    public static void main(String[] args) {
        System.out.println(validTree(5, new int[][]{{0, 1}, {0, 2}, {0, 3}, {1, 4}}));
        System.out.println(validTree(5, new int[][]{{0, 1}, {1, 2}, {2, 3}, {1, 3}, {1, 4}}));
        System.out.println(validTree(4, new int[][]{{0, 1}, {2, 3}, {1, 0}}));
    }
}
true
false
false

4. Print the cycle. In a directed graph, print the vertices of a cycle you found.

Solution

When the iterative DFS hits a grey w, the cycle is the stack from w up to the top, then back to w.

import java.util.*;

public class Main {
    // Print the vertices of a directed cycle: the grey vertices on the stack, from w (the grey one we hit) to the top.
    static List<Integer> findCycle(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);
        int[] color = new int[n], next = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (color[s] != 0) continue;
            color[s] = 1; st.push(s);
            while (!st.isEmpty()) {
                int v = st.peek();
                if (next[v] < adj.get(v).size()) {
                    int w = adj.get(v).get(next[v]++);
                    if (color[w] == 1) {                       // the path from w to v, then back to w
                        List<Integer> path = new ArrayList<>(st);  // top first
                        Collections.reverse(path);                  // bottom first
                        List<Integer> cyc = new ArrayList<>(path.subList(path.indexOf(w), path.size()));
                        cyc.add(w);
                        return cyc;
                    }
                    if (color[w] == 0) { color[w] = 1; st.push(w); }
                } else { color[v] = 2; st.pop(); }
            }
        }
        return List.of();
    }
    public static void main(String[] args) {
        System.out.println(findCycle(4, new int[][]{{0, 3}, {3, 1}, {1, 2}, {2, 3}}));
        System.out.println(findCycle(4, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}}));
    }
}
[3, 1, 2, 3]
[]

Quick quiz

Which directed graph has a cycle?

A: 0→1, 1→2, 0→2
B: 0→1, 1→2, 2→1
C: 0→1, 2→1, 2→0
D: 0→1, 0→2, 2→1
Answer

B. 1 → 2 → 1 is a loop. A, C and D each reach some vertex by two roads, but none can come back: two roads are not a cycle when the edges are one-way.

Interview questions

  1. Why can't you use the same algorithm for undirected and directed graphs? Undirected: any second road to a seen vertex (other than the cable back to the parent) is a loop. Directed: two roads to a vertex are not a loop; only an arrow back to a vertex still on the current path (grey) is.
  2. What do grey and black mean, and why do you need both? Grey = still on the current path; black = finished. With only "visited", a finished vertex reached by a second road (the diamond) would look like a cycle.
  3. How else can you detect a directed cycle? Kahn's algorithm (episode 51): if fewer than n vertices come out of the in-degree queue, there is a cycle.
  4. How do you detect an undirected cycle with union-find? For each edge, if its two ends are already in the same group, it closes a cycle; otherwise union them. O(E × α(V)).
  5. A recursive DFS crashed on a big input. What do you do? Replace the recursion with your own stack plus a "next neighbour" pointer per vertex (or increase the thread stack size, which is a workaround, not a fix).
  6. How many edges can a forest (no cycle) on n vertices have? At most n - 1 (exactly n - 1 if it is one tree). So E ≥ n in an undirected graph guarantees a cycle.

Glossary

Term Meaning
Vertex / edge A point / a link between two points
Undirected edge Works both ways; stored in both lists
Directed edge One way, a → b; stored in a's list
Path A walk along edges
Cycle A path back to its start, no edge used twice
Self-loop An edge from a vertex to itself
Tree / forest A connected graph with no cycle / several trees
Parent The vertex that discovered v first in a BFS or DFS
Broadcast storm Network messages circling a cable loop forever
Circular reference Spreadsheet formulas that need each other in a loop
DFS Depth-first search: one path as deep as possible, then step back
White / grey / black Not visited / on the current path / finished
Call stack The calls that have started but not returned
StackOverflowError Java's error when the call stack runs out
Iterative DFS DFS with our own stack instead of recursion
next[v] Which of v's arrows the iterative DFS tries next
Diamond Two roads to the same vertex, no cycle
Union-find (DSU) Groups with leaders; find and union in almost O(1)
O(V + E) Time that grows with vertices plus edges

Summary

  • Undirected: one BFS; a seen neighbour that isn't the parent is a second road, so a cycle. O(V + E).
  • Directed: two roads are not a loop. DFS with white, grey, black; an arrow to a grey vertex is a cycle; paint black when finished.
  • Deep graphs overflow recursion: use your own stack with a next[] pointer.
  • Each algorithm for its own kind of graph.
  • Next episode: topological sort (Kahn's algorithm): when there's no cycle, put everything in order.