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 ofv. - Undirected edge
{a, b}: can be walked both ways. We store it twice:bina's list andainb's list. - Directed edge
a → b: one way only. Stored once, ina'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
nvertices has exactlyn - 1edges; one more edge always makes a cycle. - Parent (in a BFS/DFS): the vertex that discovered
vfirst. - 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 to3, 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:
wis grey:wis still on our current path, so we walked in a circle back to it. Cycle.wis black: fully explored earlier, nothing below it loops. Skip it (this is the diamond's3).wis 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.
- Look at the top
v. If it has an arrow left, take it (next[v]++): grey → cycle; white → paint grey and push. - 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
- 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.
- 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.
- How else can you detect a directed cycle? Kahn's algorithm (episode 51): if fewer than
nvertices come out of the in-degree queue, there is a cycle. - 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)).
- 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).
- How many edges can a forest (no cycle) on n vertices have? At most
n - 1(exactlyn - 1if it is one tree). SoE ≥ nin 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.