What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Graph Algorithms

Builds on Flood Fill, which you haven’t finished yet.

P2MediumBuilt on Flood Fill~5 min speedrun

Cycle Detection in an Undirected Graph (Parent Check)

Built on

Flood FillThe search remembers the node it came from, and reaching an already-seen node that is not that parent proves a cycle.

The problem

Graph Valid Tree (LC 261)(opens leetcode.com)

What a tree is (assume nothing): a tree is an undirected graph in which every node can reach every other node, and no cycle exists. A cycle is a path of edges that starts and ends at the same node without using an edge twice.

You get n, the number of nodes, numbered 0 to n - 1. You also get edges, a list of pairs. Each pair [a, b] is an undirected edge: it joins node a and node b, and it can be walked in both directions.

Return true when these edges make one tree. Return false otherwise.

Example 1

Input:n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

Output:true

Node 0 joins nodes 1, 2 and 3, and node 1 joins node 4. All five nodes are in one group and no edge closes a loop.

Undirected Cycle

graph ➔ remember the parent ➔ a seen node that is not the parent is a cycle

Spot it when: You must tell whether an undirected graph has a cycle, whether it is a tree (connected and without a cycle), or which edge closes a loop.

Undirected Cycle

Python

1	from typing import List
2
3
4	def has_cycle_undirected(n: int, edges: List[List[int]]) -> bool:
5	"""Cycle detection in an undirected graph: the search remembers the node it came
6	from.
7	Time: O(V + E) \| Space: O(V + E)
8	"""
9	# adj[u] lists the neighbours of u; every edge is stored at both of its ends
10	adj = [[] for _ in range(n)]
11	for u, v in edges:
12	adj[u].append(v)
13	adj[v].append(u)
14
15	seen = [False] * n # seen[u] is True once a search has reached u
16	# 1. Start A Search From Every Unseen Node:
17	# The graph may be disconnected, so a node that no earlier search reached starts its
18	# own search.
19	for start in range(n):
20	if seen[start]:
21	continue
22	seen[start] = True
23	# (node, the node it was reached from); the first node of a search has none, so
24	# -1
25	stack = [(start, -1)]
26	while stack:
27	u, parent = stack.pop()
28	for v in adj[u]:
29	# 2. Skip The Edge Back To The Parent:
30	# This is the edge the search just used, and parent is always seen. It
31	# is the same edge, not a second route.
32	if v == parent:
33	continue
34	# 3. Any Other Edge To A Seen Node Closes A Cycle:
35	# v was reached before by another route, so u and v are joined by two
36	# different routes.
37	if seen[v]:
38	return True
39	seen[v] = True # Mark on push, not on pop
40	stack.append((v, u))
41	return False

Invariant: Every edge scanned so far either reached a new node or led back to the parent of the node that scanned it, because any other edge to a seen node returns True at once.

Store each node with the node it came from: stack.append((v, u)) makes u the parent of v. An undirected edge is stored at both of its ends, so the scan of v meets the edge back to parent. That edge is the one the search just used, so if v == parent: continue skips it. Any other edge from u to a node that is already in seen is a second route between those two nodes, so return True. This is correct because each node enters seen once, from one parent, so the parent edges form a forest, which is a graph with no cycle. A forest has exactly one path between two nodes, so every other edge between two seen nodes closes a cycle. The trap is the skip: without if v == parent: continue, the edge back to parent finds parent already in seen, so every graph that has an edge looks like it has a cycle.

See it run

Graph Valid Tree with a parent check, step by step

reached 1

Each circle is a node. The tag under it says whether the search has seen it. The row under the graph is the stack: the last box leaves first.

scan the node just taken from the stack
seen the search has reached this node
parent the edge the search came by, which is skipped
cycle an edge to a seen node that is not the parent

The graph has 5 nodes and 5 edges. The search starts at node 0: seen[0] is True, reached is 1, and the stack holds (0, -1).

stack (last in, first out)

(0, -1)

1 / 9

Gotchas1 of 5

The trap
Gotcha 1: Leaving out the check for the edge back to parent
Mistake
```
# no check for the parent
```
Fix
```
if v == parent:
    continue
```
What happens: Every edge is stored at both of its ends. When the search goes from u to v, the scan of v meets the edge back to u. At that moment u is already in seen. Without the skip, if seen[v] is True for this edge, and the function returns True. So any graph with at least one edge is reported as having a cycle, even a graph of two nodes with one edge.
Example: n = 2, edges = [[0, 1]]
Mistake: returns TrueFix: returns False
Gotcha 2: Storing neighbours in a set when an edge can repeat
Mistake
```
adj = [set() for _ in range(n)]
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)
```
Fix
```
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
```
What happens: A set keeps one copy of each neighbour. Two edges between the same two nodes, [0, 1] and [0, 1], become one edge. Two edges between the same pair of nodes are a cycle of two nodes. With a list, adj[0] is [1, 1]. The first copy reaches node 1. The second copy finds node 1 already in seen, and node 1 is not the parent of node 0, so the function returns True. With a set, adj[0] is {1} and the cycle disappears. Graph Valid Tree (LC 261) never repeats an edge, so this mistake passes there. It fails on an input where an edge can repeat.
Example: n = 2, edges = [[0, 1], [0, 1]]
Mistake: returns FalseFix: returns True
Gotcha 3: Starting the search from node 0 only
Mistake
```
for start in [0]:
```
Fix
```
for start in range(n):
```
What happens: The graph can have several connected groups. A search from node 0 reaches only the nodes that connect to node 0. In the example, nodes 2, 3 and 4 form a triangle that node 0 never reaches, so the cycle is never found. for start in range(n) begins a new search at every node that is not in seen yet.
Example: n = 5, edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Mistake: returns FalseFix: returns True
Gotcha 4: Ending validTree with return True instead of return reached == n
Mistake
```
return True
```
Fix
```
return reached == n
```
What happens: A tree is connected and has no cycle. The search from node 0 finds a cycle only in the group of node 0. It never looks at a node in another group. In the example, the search reaches nodes 0 and 1, so reached is 2 and n is 4. Nodes 2 and 3 are in a separate group. return True accepts this graph, which is a forest and not one tree.
Example: n = 4, edges = [[0, 1], [2, 3]]
Mistake: returns TrueFix: returns False
Gotcha 5: Using the parent check on a directed graph
Mistake
```
has_cycle_undirected(4, [[0, 1], [0, 2], [1, 3], [2, 3]])
```
Fix
```
has_cycle_directed(4, [[0, 1], [0, 2], [1, 3], [2, 3]])
```
What happens: The template stores every edge at both of its ends, so it ignores the direction of each arrow. The arrows 0 -> 1, 0 -> 2, 1 -> 3 and 2 -> 3 give two routes from node 0 to node 3. These two routes are not a directed cycle, because no arrow leads back to node 0. Without the directions, the same four edges form the cycle 0, 1, 3, 2. So the template returns True and the directed answer is False. A directed graph needs a state for a node that is on the current path, and a seen flag with a parent cannot give it. See Cycle Detection in a Directed Graph (DFS Three-Color).
Example: n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3]] as one-way arrows
Mistake: returns TrueFix: returns False

Not this one if…

The edges are one-way arrows and you must find a loop that follows the arrows, as in Course Schedule (LC 207). The parent check reports a node reached by two routes as a cycle, but in a directed graph two routes to one node are not a cycle. See Cycle Detection
You must split the nodes into two groups so that every edge joins different groups, as in Is Graph Bipartite? (LC 785). Only a cycle with an odd number of edges breaks that split, but this card reports a cycle of any length. See Bipartite Check
The edges arrive one at a time and the answer is needed after every edge, as in Number of Islands II (LC 305). Searching the whole graph again after each edge repeats the same work. See Union-Find

Deep Dive

Why the edge back to the parent is not a cycle

An undirected edge joins two nodes in both directions. The code stores it twice: adj[u] holds v, and adj[v] holds u.

Suppose the search goes from u to v. When the search pops v, it scans adj[v], and that list holds u. This is the same edge, walked the other way. It is not a second route to u.

This is why each stack entry carries its parent. The line if v == parent: continue skips exactly the edge the search just used.

Example: n = 2 and edges = [[0, 1]]. Node 0 pushes (1, 0). Node 1 scans adj[1] = [0]. Node 0 is the parent, so it is skipped, and the function reports no cycle. Without the skip, node 0 is already seen, and the single edge is reported as a cycle.

Why any other edge to a seen node is a cycle

Each node enters seen exactly once, and it enters together with one parent. So every seen node, except node 0, has exactly one edge that led to it. These edges form a forest. A forest is a graph with no cycle.

In a forest, two nodes have exactly one path between them. Now suppose the scan of u finds an edge to a seen node v, and v is not the parent of u. The search already linked u and v through the forest. This extra edge is a second route between them, and two routes make a cycle.

Example: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]. Node 2 and node 3 were both reached from node 1. When node 3 scans its neighbour 2, node 2 is seen, and node 2 is not the parent of node 3, which is node 1. The cycle is 1, 2, 3.

A repeated edge works the same way. With edges = [[0, 1], [0, 1]], adj[0] is [1, 1]. The first copy reaches node 1. The second copy finds node 1 already seen, and node 1 is not the parent of node 0, so the function reports a cycle of two nodes. This is correct, and it is why adj must be a list that keeps both copies.

One trace: the edge 2-3 closes the cycle

The board runs validTree on LeetCode's Example 2: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]].

Pop (0, -1). Node 1 is new, so it is marked seen and (1, 0) goes on the stack. Pop (1, 0). Neighbour 0 is the parent, so that edge is skipped. This is the step marked with the trap tag on the board. Neighbours 2, 3 and 4 are new, so each is marked seen and pushed with parent 1.

Pop (4, 1). Its only neighbour is its parent, so it is skipped. Pop (3, 1). Its neighbour list is [2, 1]. Node 2 is already seen, and node 2 is not the parent of node 3. The edge 3-2 closes a cycle, and the function returns False.

At that moment reached is 5, so the nodes are all connected. Connection alone does not make a tree. A tree has no cycle, and this graph has one.

A tree also needs one group, and the cost

A tree is a graph with no cycle in which every node is connected. The cycle check covers the first part. The last line return reached == n covers the second part. A forest, such as n = 4 and edges = [[0, 1], [2, 3]], has no cycle, but the search from node 0 reaches only 2 of the 4 nodes, so the answer is False.

The edge count alone is not enough either. For n = 4 and edges = [[0, 1], [1, 2], [2, 0]], there are n - 1 = 3 edges, but they form a triangle and node 3 is alone. The parent check finds the triangle, and the function returns False.

Each node is pushed once, and each edge is read from both ends. So the time is O(V + E), where V is the number of nodes and E is the number of edges. adj holds 2E entries, and seen and stack hold at most V entries each, so the space is O(V + E).

The same check solves other problems. Redundant Connection (LC 684) has one extra edge, and the first edge to a seen node lies on the only cycle. Detect Cycles in 2D Grid (LC 1559) treats each cell as a node, and the parent is the cell the search came from. Shortest Cycle in a Graph (LC 2608) runs the check inside a BFS from every node, and it measures each cycle as dist[u] + dist[v] + 1.

60-Second Pitch

"A tree is a graph with no cycle in which every node is connected, so I check both parts with one search from node 0. I keep a stack of pairs. Each pair holds a node and the node it came from, its parent. When I scan a neighbour, I first skip the parent, because that edge is the one I just used. If the neighbour is any other node that is already seen, the search has linked those two nodes by another route, so there is a cycle and I return False. Otherwise I mark the neighbour seen, count it and push it. At the end I return whether the count of reached nodes equals n. If it is smaller, some nodes are in a separate group. Each node is pushed once and each edge is read twice, so the time is O(V + E) and the space is O(V + E)."

Common Questions

Why compare with the parent only, and not with every node that is already seen?: Only the parent is certain to be seen because of the edge the search just used. Every other seen node was reached by another route. If a different seen node shows up in adj[u], then u has an edge that is not part of the forest, and that edge closes a cycle. So the parent is the single seen node that is allowed.
Does this work when the same edge appears twice?: Yes, as long as adj is a list. With edges = [[0, 1], [0, 1]], adj[0] is [1, 1]. The first copy reaches node 1. The second copy finds node 1 seen and not the parent of node 0, so the function reports a cycle of two nodes. A set would store node 1 once and lose the cycle.
Can you use BFS in place of DFS?: Yes. The proof needs only that each node is marked once, when it is first reached, together with the node it came from. A queue does that too. Shortest Cycle in a Graph (LC 2608) uses BFS for this reason, and it reads the cycle length from the dist values of the two nodes.
How is this different from Cycle Detection in a Directed Graph (DFS Three-Color)?: In a directed graph, two routes to one node do not make a cycle. The arrows must lead back to a node on the current path. The directed card therefore keeps a state for a node that is on the current path. The parent check only works for undirected edges, where two routes always close a loop.
What are the cost, and when would you use union-find instead?: The search takes O(V + E) time and O(V + E) space. Use union-find when the edges arrive one at a time and you need the answer after each new edge, as in Number of Islands II (LC 305). Union-find answers each new edge in nearly constant time, while this search needs the whole graph first.

SWE Reasoning

Spot it

The statement asks whether an undirected graph is a tree, has a cycle, or which edge closes a loop.
A tree means two things: no cycle, and all nodes in one connected group. Say both parts out loud.
The graph is given as a list of edges, and the whole list is known before the answer is needed.
A cycle in a grid, where each cell is a node, uses the same check with a parent cell.
If the edges have directions, this is a different card.

The invariant, step by step

adj stores every edge at both of its ends. seen[0] is True, reached is 1, and stack holds (0, -1).
Each pop returns (u, parent). The scan of u looks at every neighbour v.
If v == parent, the edge is the one the search used to reach u. Skip it.
If seen[v] is True and v is not the parent, u and v are already linked by another route. Return False.
Otherwise v is new. Mark it seen, add 1 to reached, and push (v, u).
When the stack is empty, there is no cycle. The graph is a tree only if reached == n.

Traps

Starting reached at 0. Node 0 is marked seen before the loop, so it counts as reached. With reached = 0, Example 1 ends with reached = 4 and returns False for a tree.
Trusting the edge count. len(edges) == n - 1 does not rule out a cycle. The triangle [[0, 1], [1, 2], [2, 0]] with n = 4 has 3 edges and still has a cycle.
Recursion on a long path. A recursive search on a path of 2000 nodes needs about 2000 nested calls, and Python's default limit is 1000, so it raises a RecursionError. The explicit stack has no such limit.
One node. n = 1 and edges = [] is a tree. The loop does not run, and reached == n is 1 == 1, so the answer is True.

Practice

Canonical LeetCode:Graph Valid Tree (LC 261)Redundant Connection (LC 684)Detect Cycles in 2D Grid (LC 1559)Shortest Cycle in a Graph (LC 2608)

Theory Context•Graph Algorithms

Builds on Flood Fill, which you haven’t finished yet.

P2MediumBuilt on Flood Fill~5 min speedrun

Cycle Detection in an Undirected Graph (Parent Check)

Built on

Flood FillThe search remembers the node it came from, and reaching an already-seen node that is not that parent proves a cycle.

The problem

Graph Valid Tree (LC 261)(opens leetcode.com)

Return true when these edges make one tree. Return false otherwise.

Example 1

Input:n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

Output:true

Node 0 joins nodes 1, 2 and 3, and node 1 joins node 4. All five nodes are in one group and no edge closes a loop.

Undirected Cycle

graph ➔ remember the parent ➔ a seen node that is not the parent is a cycle

Spot it when: You must tell whether an undirected graph has a cycle, whether it is a tree (connected and without a cycle), or which edge closes a loop.

Undirected Cycle

Python

1	from typing import List
2
3
4	def has_cycle_undirected(n: int, edges: List[List[int]]) -> bool:
5	"""Cycle detection in an undirected graph: the search remembers the node it came
6	from.
7	Time: O(V + E) \| Space: O(V + E)
8	"""
9	# adj[u] lists the neighbours of u; every edge is stored at both of its ends
10	adj = [[] for _ in range(n)]
11	for u, v in edges:
12	adj[u].append(v)
13	adj[v].append(u)
14
15	seen = [False] * n # seen[u] is True once a search has reached u
16	# 1. Start A Search From Every Unseen Node:
17	# The graph may be disconnected, so a node that no earlier search reached starts its
18	# own search.
19	for start in range(n):
20	if seen[start]:
21	continue
22	seen[start] = True
23	# (node, the node it was reached from); the first node of a search has none, so
24	# -1
25	stack = [(start, -1)]
26	while stack:
27	u, parent = stack.pop()
28	for v in adj[u]:
29	# 2. Skip The Edge Back To The Parent:
30	# This is the edge the search just used, and parent is always seen. It
31	# is the same edge, not a second route.
32	if v == parent:
33	continue
34	# 3. Any Other Edge To A Seen Node Closes A Cycle:
35	# v was reached before by another route, so u and v are joined by two
36	# different routes.
37	if seen[v]:
38	return True
39	seen[v] = True # Mark on push, not on pop
40	stack.append((v, u))
41	return False

Invariant: Every edge scanned so far either reached a new node or led back to the parent of the node that scanned it, because any other edge to a seen node returns True at once.

See it run

Graph Valid Tree with a parent check, step by step

reached 1

Each circle is a node. The tag under it says whether the search has seen it. The row under the graph is the stack: the last box leaves first.

scan the node just taken from the stack
seen the search has reached this node
parent the edge the search came by, which is skipped
cycle an edge to a seen node that is not the parent

The graph has 5 nodes and 5 edges. The search starts at node 0: seen[0] is True, reached is 1, and the stack holds (0, -1).

stack (last in, first out)

(0, -1)

1 / 9

Gotchas1 of 5

The trap
Gotcha 1: Leaving out the check for the edge back to parent
Mistake
```
# no check for the parent
```
Fix
```
if v == parent:
    continue
```
What happens: Every edge is stored at both of its ends. When the search goes from u to v, the scan of v meets the edge back to u. At that moment u is already in seen. Without the skip, if seen[v] is True for this edge, and the function returns True. So any graph with at least one edge is reported as having a cycle, even a graph of two nodes with one edge.
Example: n = 2, edges = [[0, 1]]
Mistake: returns TrueFix: returns False
Gotcha 2: Storing neighbours in a set when an edge can repeat
Mistake
```
adj = [set() for _ in range(n)]
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)
```
Fix
```
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
```
What happens: A set keeps one copy of each neighbour. Two edges between the same two nodes, [0, 1] and [0, 1], become one edge. Two edges between the same pair of nodes are a cycle of two nodes. With a list, adj[0] is [1, 1]. The first copy reaches node 1. The second copy finds node 1 already in seen, and node 1 is not the parent of node 0, so the function returns True. With a set, adj[0] is {1} and the cycle disappears. Graph Valid Tree (LC 261) never repeats an edge, so this mistake passes there. It fails on an input where an edge can repeat.
Example: n = 2, edges = [[0, 1], [0, 1]]
Mistake: returns FalseFix: returns True
Gotcha 3: Starting the search from node 0 only
Mistake
```
for start in [0]:
```
Fix
```
for start in range(n):
```
What happens: The graph can have several connected groups. A search from node 0 reaches only the nodes that connect to node 0. In the example, nodes 2, 3 and 4 form a triangle that node 0 never reaches, so the cycle is never found. for start in range(n) begins a new search at every node that is not in seen yet.
Example: n = 5, edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Mistake: returns FalseFix: returns True
Gotcha 4: Ending validTree with return True instead of return reached == n
Mistake
```
return True
```
Fix
```
return reached == n
```
What happens: A tree is connected and has no cycle. The search from node 0 finds a cycle only in the group of node 0. It never looks at a node in another group. In the example, the search reaches nodes 0 and 1, so reached is 2 and n is 4. Nodes 2 and 3 are in a separate group. return True accepts this graph, which is a forest and not one tree.
Example: n = 4, edges = [[0, 1], [2, 3]]
Mistake: returns TrueFix: returns False
Gotcha 5: Using the parent check on a directed graph
Mistake
```
has_cycle_undirected(4, [[0, 1], [0, 2], [1, 3], [2, 3]])
```
Fix
```
has_cycle_directed(4, [[0, 1], [0, 2], [1, 3], [2, 3]])
```
What happens: The template stores every edge at both of its ends, so it ignores the direction of each arrow. The arrows 0 -> 1, 0 -> 2, 1 -> 3 and 2 -> 3 give two routes from node 0 to node 3. These two routes are not a directed cycle, because no arrow leads back to node 0. Without the directions, the same four edges form the cycle 0, 1, 3, 2. So the template returns True and the directed answer is False. A directed graph needs a state for a node that is on the current path, and a seen flag with a parent cannot give it. See Cycle Detection in a Directed Graph (DFS Three-Color).
Example: n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3]] as one-way arrows
Mistake: returns TrueFix: returns False

Not this one if…

The edges are one-way arrows and you must find a loop that follows the arrows, as in Course Schedule (LC 207). The parent check reports a node reached by two routes as a cycle, but in a directed graph two routes to one node are not a cycle. See Cycle Detection
You must split the nodes into two groups so that every edge joins different groups, as in Is Graph Bipartite? (LC 785). Only a cycle with an odd number of edges breaks that split, but this card reports a cycle of any length. See Bipartite Check
The edges arrive one at a time and the answer is needed after every edge, as in Number of Islands II (LC 305). Searching the whole graph again after each edge repeats the same work. See Union-Find

Deep Dive

Why the edge back to the parent is not a cycle

An undirected edge joins two nodes in both directions. The code stores it twice: adj[u] holds v, and adj[v] holds u.

Suppose the search goes from u to v. When the search pops v, it scans adj[v], and that list holds u. This is the same edge, walked the other way. It is not a second route to u.

This is why each stack entry carries its parent. The line if v == parent: continue skips exactly the edge the search just used.

Why any other edge to a seen node is a cycle

One trace: the edge 2-3 closes the cycle

The board runs validTree on LeetCode's Example 2: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]].

At that moment reached is 5, so the nodes are all connected. Connection alone does not make a tree. A tree has no cycle, and this graph has one.

A tree also needs one group, and the cost

60-Second Pitch

Common Questions

Why compare with the parent only, and not with every node that is already seen?: Only the parent is certain to be seen because of the edge the search just used. Every other seen node was reached by another route. If a different seen node shows up in adj[u], then u has an edge that is not part of the forest, and that edge closes a cycle. So the parent is the single seen node that is allowed.
Does this work when the same edge appears twice?: Yes, as long as adj is a list. With edges = [[0, 1], [0, 1]], adj[0] is [1, 1]. The first copy reaches node 1. The second copy finds node 1 seen and not the parent of node 0, so the function reports a cycle of two nodes. A set would store node 1 once and lose the cycle.
Can you use BFS in place of DFS?: Yes. The proof needs only that each node is marked once, when it is first reached, together with the node it came from. A queue does that too. Shortest Cycle in a Graph (LC 2608) uses BFS for this reason, and it reads the cycle length from the dist values of the two nodes.
How is this different from Cycle Detection in a Directed Graph (DFS Three-Color)?: In a directed graph, two routes to one node do not make a cycle. The arrows must lead back to a node on the current path. The directed card therefore keeps a state for a node that is on the current path. The parent check only works for undirected edges, where two routes always close a loop.
What are the cost, and when would you use union-find instead?: The search takes O(V + E) time and O(V + E) space. Use union-find when the edges arrive one at a time and you need the answer after each new edge, as in Number of Islands II (LC 305). Union-find answers each new edge in nearly constant time, while this search needs the whole graph first.

SWE Reasoning

Spot it

The statement asks whether an undirected graph is a tree, has a cycle, or which edge closes a loop.
A tree means two things: no cycle, and all nodes in one connected group. Say both parts out loud.
The graph is given as a list of edges, and the whole list is known before the answer is needed.
A cycle in a grid, where each cell is a node, uses the same check with a parent cell.
If the edges have directions, this is a different card.

The invariant, step by step

adj stores every edge at both of its ends. seen[0] is True, reached is 1, and stack holds (0, -1).
Each pop returns (u, parent). The scan of u looks at every neighbour v.
If v == parent, the edge is the one the search used to reach u. Skip it.
If seen[v] is True and v is not the parent, u and v are already linked by another route. Return False.
Otherwise v is new. Mark it seen, add 1 to reached, and push (v, u).
When the stack is empty, there is no cycle. The graph is a tree only if reached == n.

Traps

Starting reached at 0. Node 0 is marked seen before the loop, so it counts as reached. With reached = 0, Example 1 ends with reached = 4 and returns False for a tree.
Trusting the edge count. len(edges) == n - 1 does not rule out a cycle. The triangle [[0, 1], [1, 2], [2, 0]] with n = 4 has 3 edges and still has a cycle.
Recursion on a long path. A recursive search on a path of 2000 nodes needs about 2000 nested calls, and Python's default limit is 1000, so it raises a RecursionError. The explicit stack has no such limit.
One node. n = 1 and edges = [] is a tree. The loop does not run, and reached == n is 1 == 1, so the answer is True.

Practice

Canonical LeetCode:Graph Valid Tree (LC 261)Redundant Connection (LC 684)Detect Cycles in 2D Grid (LC 1559)Shortest Cycle in a Graph (LC 2608)

Theory Context•Graph Algorithms

Builds on Flood Fill, which you haven’t finished yet.

P2MediumBuilt on Flood Fill~5 min speedrun

Cycle Detection in an Undirected Graph (Parent Check)

Built on

Flood FillThe search remembers the node it came from, and reaching an already-seen node that is not that parent proves a cycle.

The problem

Graph Valid Tree (LC 261)(opens leetcode.com)

Return true when these edges make one tree. Return false otherwise.

Example 1

Input:n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

Output:true

Node 0 joins nodes 1, 2 and 3, and node 1 joins node 4. All five nodes are in one group and no edge closes a loop.

Undirected Cycle

graph ➔ remember the parent ➔ a seen node that is not the parent is a cycle

Spot it when: You must tell whether an undirected graph has a cycle, whether it is a tree (connected and without a cycle), or which edge closes a loop.

Undirected Cycle

Python

1	from typing import List
2
3
4	def has_cycle_undirected(n: int, edges: List[List[int]]) -> bool:
5	"""Cycle detection in an undirected graph: the search remembers the node it came
6	from.
7	Time: O(V + E) \| Space: O(V + E)
8	"""
9	# adj[u] lists the neighbours of u; every edge is stored at both of its ends
10	adj = [[] for _ in range(n)]
11	for u, v in edges:
12	adj[u].append(v)
13	adj[v].append(u)
14
15	seen = [False] * n # seen[u] is True once a search has reached u
16	# 1. Start A Search From Every Unseen Node:
17	# The graph may be disconnected, so a node that no earlier search reached starts its
18	# own search.
19	for start in range(n):
20	if seen[start]:
21	continue
22	seen[start] = True
23	# (node, the node it was reached from); the first node of a search has none, so
24	# -1
25	stack = [(start, -1)]
26	while stack:
27	u, parent = stack.pop()
28	for v in adj[u]:
29	# 2. Skip The Edge Back To The Parent:
30	# This is the edge the search just used, and parent is always seen. It
31	# is the same edge, not a second route.
32	if v == parent:
33	continue
34	# 3. Any Other Edge To A Seen Node Closes A Cycle:
35	# v was reached before by another route, so u and v are joined by two
36	# different routes.
37	if seen[v]:
38	return True
39	seen[v] = True # Mark on push, not on pop
40	stack.append((v, u))
41	return False

Invariant: Every edge scanned so far either reached a new node or led back to the parent of the node that scanned it, because any other edge to a seen node returns True at once.

See it run

Graph Valid Tree with a parent check, step by step

reached 1

Each circle is a node. The tag under it says whether the search has seen it. The row under the graph is the stack: the last box leaves first.

scan the node just taken from the stack
seen the search has reached this node
parent the edge the search came by, which is skipped
cycle an edge to a seen node that is not the parent

The graph has 5 nodes and 5 edges. The search starts at node 0: seen[0] is True, reached is 1, and the stack holds (0, -1).

stack (last in, first out)

(0, -1)

1 / 9

Gotchas1 of 5

The trap
Gotcha 1: Leaving out the check for the edge back to parent
Mistake
```
# no check for the parent
```
Fix
```
if v == parent:
    continue
```
What happens: Every edge is stored at both of its ends. When the search goes from u to v, the scan of v meets the edge back to u. At that moment u is already in seen. Without the skip, if seen[v] is True for this edge, and the function returns True. So any graph with at least one edge is reported as having a cycle, even a graph of two nodes with one edge.
Example: n = 2, edges = [[0, 1]]
Mistake: returns TrueFix: returns False
Gotcha 2: Storing neighbours in a set when an edge can repeat
Mistake
```
adj = [set() for _ in range(n)]
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)
```
Fix
```
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
```
What happens: A set keeps one copy of each neighbour. Two edges between the same two nodes, [0, 1] and [0, 1], become one edge. Two edges between the same pair of nodes are a cycle of two nodes. With a list, adj[0] is [1, 1]. The first copy reaches node 1. The second copy finds node 1 already in seen, and node 1 is not the parent of node 0, so the function returns True. With a set, adj[0] is {1} and the cycle disappears. Graph Valid Tree (LC 261) never repeats an edge, so this mistake passes there. It fails on an input where an edge can repeat.
Example: n = 2, edges = [[0, 1], [0, 1]]
Mistake: returns FalseFix: returns True
Gotcha 3: Starting the search from node 0 only
Mistake
```
for start in [0]:
```
Fix
```
for start in range(n):
```
What happens: The graph can have several connected groups. A search from node 0 reaches only the nodes that connect to node 0. In the example, nodes 2, 3 and 4 form a triangle that node 0 never reaches, so the cycle is never found. for start in range(n) begins a new search at every node that is not in seen yet.
Example: n = 5, edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Mistake: returns FalseFix: returns True
Gotcha 4: Ending validTree with return True instead of return reached == n
Mistake
```
return True
```
Fix
```
return reached == n
```
What happens: A tree is connected and has no cycle. The search from node 0 finds a cycle only in the group of node 0. It never looks at a node in another group. In the example, the search reaches nodes 0 and 1, so reached is 2 and n is 4. Nodes 2 and 3 are in a separate group. return True accepts this graph, which is a forest and not one tree.
Example: n = 4, edges = [[0, 1], [2, 3]]
Mistake: returns TrueFix: returns False
Gotcha 5: Using the parent check on a directed graph
Mistake
```
has_cycle_undirected(4, [[0, 1], [0, 2], [1, 3], [2, 3]])
```
Fix
```
has_cycle_directed(4, [[0, 1], [0, 2], [1, 3], [2, 3]])
```
What happens: The template stores every edge at both of its ends, so it ignores the direction of each arrow. The arrows 0 -> 1, 0 -> 2, 1 -> 3 and 2 -> 3 give two routes from node 0 to node 3. These two routes are not a directed cycle, because no arrow leads back to node 0. Without the directions, the same four edges form the cycle 0, 1, 3, 2. So the template returns True and the directed answer is False. A directed graph needs a state for a node that is on the current path, and a seen flag with a parent cannot give it. See Cycle Detection in a Directed Graph (DFS Three-Color).
Example: n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3]] as one-way arrows
Mistake: returns TrueFix: returns False

Not this one if…

The edges are one-way arrows and you must find a loop that follows the arrows, as in Course Schedule (LC 207). The parent check reports a node reached by two routes as a cycle, but in a directed graph two routes to one node are not a cycle. See Cycle Detection
You must split the nodes into two groups so that every edge joins different groups, as in Is Graph Bipartite? (LC 785). Only a cycle with an odd number of edges breaks that split, but this card reports a cycle of any length. See Bipartite Check
The edges arrive one at a time and the answer is needed after every edge, as in Number of Islands II (LC 305). Searching the whole graph again after each edge repeats the same work. See Union-Find

Deep Dive

Why the edge back to the parent is not a cycle

An undirected edge joins two nodes in both directions. The code stores it twice: adj[u] holds v, and adj[v] holds u.

Suppose the search goes from u to v. When the search pops v, it scans adj[v], and that list holds u. This is the same edge, walked the other way. It is not a second route to u.

This is why each stack entry carries its parent. The line if v == parent: continue skips exactly the edge the search just used.

Why any other edge to a seen node is a cycle

One trace: the edge 2-3 closes the cycle

The board runs validTree on LeetCode's Example 2: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]].

At that moment reached is 5, so the nodes are all connected. Connection alone does not make a tree. A tree has no cycle, and this graph has one.

A tree also needs one group, and the cost

60-Second Pitch

Common Questions

Why compare with the parent only, and not with every node that is already seen?: Only the parent is certain to be seen because of the edge the search just used. Every other seen node was reached by another route. If a different seen node shows up in adj[u], then u has an edge that is not part of the forest, and that edge closes a cycle. So the parent is the single seen node that is allowed.
Does this work when the same edge appears twice?: Yes, as long as adj is a list. With edges = [[0, 1], [0, 1]], adj[0] is [1, 1]. The first copy reaches node 1. The second copy finds node 1 seen and not the parent of node 0, so the function reports a cycle of two nodes. A set would store node 1 once and lose the cycle.
Can you use BFS in place of DFS?: Yes. The proof needs only that each node is marked once, when it is first reached, together with the node it came from. A queue does that too. Shortest Cycle in a Graph (LC 2608) uses BFS for this reason, and it reads the cycle length from the dist values of the two nodes.
How is this different from Cycle Detection in a Directed Graph (DFS Three-Color)?: In a directed graph, two routes to one node do not make a cycle. The arrows must lead back to a node on the current path. The directed card therefore keeps a state for a node that is on the current path. The parent check only works for undirected edges, where two routes always close a loop.
What are the cost, and when would you use union-find instead?: The search takes O(V + E) time and O(V + E) space. Use union-find when the edges arrive one at a time and you need the answer after each new edge, as in Number of Islands II (LC 305). Union-find answers each new edge in nearly constant time, while this search needs the whole graph first.

SWE Reasoning

Spot it

The statement asks whether an undirected graph is a tree, has a cycle, or which edge closes a loop.
A tree means two things: no cycle, and all nodes in one connected group. Say both parts out loud.
The graph is given as a list of edges, and the whole list is known before the answer is needed.
A cycle in a grid, where each cell is a node, uses the same check with a parent cell.
If the edges have directions, this is a different card.

The invariant, step by step

adj stores every edge at both of its ends. seen[0] is True, reached is 1, and stack holds (0, -1).
Each pop returns (u, parent). The scan of u looks at every neighbour v.
If v == parent, the edge is the one the search used to reach u. Skip it.
If seen[v] is True and v is not the parent, u and v are already linked by another route. Return False.
Otherwise v is new. Mark it seen, add 1 to reached, and push (v, u).
When the stack is empty, there is no cycle. The graph is a tree only if reached == n.

Traps

Starting reached at 0. Node 0 is marked seen before the loop, so it counts as reached. With reached = 0, Example 1 ends with reached = 4 and returns False for a tree.
Trusting the edge count. len(edges) == n - 1 does not rule out a cycle. The triangle [[0, 1], [1, 2], [2, 0]] with n = 4 has 3 edges and still has a cycle.
Recursion on a long path. A recursive search on a path of 2000 nodes needs about 2000 nested calls, and Python's default limit is 1000, so it raises a RecursionError. The explicit stack has no such limit.
One node. n = 1 and edges = [] is a tree. The loop does not run, and reached == n is 1 == 1, so the answer is True.

Practice

Canonical LeetCode:Graph Valid Tree (LC 261)Redundant Connection (LC 684)Detect Cycles in 2D Grid (LC 1559)Shortest Cycle in a Graph (LC 2608)

Theory Context•Graph Algorithms

Builds on Flood Fill, which you haven’t finished yet.

P2MediumBuilt on Flood Fill~5 min speedrun

Cycle Detection in an Undirected Graph (Parent Check)

Built on

Flood FillThe search remembers the node it came from, and reaching an already-seen node that is not that parent proves a cycle.

The problem

Graph Valid Tree (LC 261)(opens leetcode.com)

Return true when these edges make one tree. Return false otherwise.

Example 1

Input:n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

Output:true

Node 0 joins nodes 1, 2 and 3, and node 1 joins node 4. All five nodes are in one group and no edge closes a loop.

Undirected Cycle

graph ➔ remember the parent ➔ a seen node that is not the parent is a cycle

Spot it when: You must tell whether an undirected graph has a cycle, whether it is a tree (connected and without a cycle), or which edge closes a loop.

Undirected Cycle

Python

1	from typing import List
2
3
4	def has_cycle_undirected(n: int, edges: List[List[int]]) -> bool:
5	"""Cycle detection in an undirected graph: the search remembers the node it came
6	from.
7	Time: O(V + E) \| Space: O(V + E)
8	"""
9	# adj[u] lists the neighbours of u; every edge is stored at both of its ends
10	adj = [[] for _ in range(n)]
11	for u, v in edges:
12	adj[u].append(v)
13	adj[v].append(u)
14
15	seen = [False] * n # seen[u] is True once a search has reached u
16	# 1. Start A Search From Every Unseen Node:
17	# The graph may be disconnected, so a node that no earlier search reached starts its
18	# own search.
19	for start in range(n):
20	if seen[start]:
21	continue
22	seen[start] = True
23	# (node, the node it was reached from); the first node of a search has none, so
24	# -1
25	stack = [(start, -1)]
26	while stack:
27	u, parent = stack.pop()
28	for v in adj[u]:
29	# 2. Skip The Edge Back To The Parent:
30	# This is the edge the search just used, and parent is always seen. It
31	# is the same edge, not a second route.
32	if v == parent:
33	continue
34	# 3. Any Other Edge To A Seen Node Closes A Cycle:
35	# v was reached before by another route, so u and v are joined by two
36	# different routes.
37	if seen[v]:
38	return True
39	seen[v] = True # Mark on push, not on pop
40	stack.append((v, u))
41	return False

Invariant: Every edge scanned so far either reached a new node or led back to the parent of the node that scanned it, because any other edge to a seen node returns True at once.

See it run

Graph Valid Tree with a parent check, step by step

reached 1

Each circle is a node. The tag under it says whether the search has seen it. The row under the graph is the stack: the last box leaves first.

scan the node just taken from the stack
seen the search has reached this node
parent the edge the search came by, which is skipped
cycle an edge to a seen node that is not the parent

The graph has 5 nodes and 5 edges. The search starts at node 0: seen[0] is True, reached is 1, and the stack holds (0, -1).

stack (last in, first out)

(0, -1)

1 / 9

Gotchas1 of 5

The trap
Gotcha 1: Leaving out the check for the edge back to parent
Mistake
```
# no check for the parent
```
Fix
```
if v == parent:
    continue
```
What happens: Every edge is stored at both of its ends. When the search goes from u to v, the scan of v meets the edge back to u. At that moment u is already in seen. Without the skip, if seen[v] is True for this edge, and the function returns True. So any graph with at least one edge is reported as having a cycle, even a graph of two nodes with one edge.
Example: n = 2, edges = [[0, 1]]
Mistake: returns TrueFix: returns False
Gotcha 2: Storing neighbours in a set when an edge can repeat
Mistake
```
adj = [set() for _ in range(n)]
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)
```
Fix
```
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
```
What happens: A set keeps one copy of each neighbour. Two edges between the same two nodes, [0, 1] and [0, 1], become one edge. Two edges between the same pair of nodes are a cycle of two nodes. With a list, adj[0] is [1, 1]. The first copy reaches node 1. The second copy finds node 1 already in seen, and node 1 is not the parent of node 0, so the function returns True. With a set, adj[0] is {1} and the cycle disappears. Graph Valid Tree (LC 261) never repeats an edge, so this mistake passes there. It fails on an input where an edge can repeat.
Example: n = 2, edges = [[0, 1], [0, 1]]
Mistake: returns FalseFix: returns True
Gotcha 3: Starting the search from node 0 only
Mistake
```
for start in [0]:
```
Fix
```
for start in range(n):
```
What happens: The graph can have several connected groups. A search from node 0 reaches only the nodes that connect to node 0. In the example, nodes 2, 3 and 4 form a triangle that node 0 never reaches, so the cycle is never found. for start in range(n) begins a new search at every node that is not in seen yet.
Example: n = 5, edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Mistake: returns FalseFix: returns True
Gotcha 4: Ending validTree with return True instead of return reached == n
Mistake
```
return True
```
Fix
```
return reached == n
```
What happens: A tree is connected and has no cycle. The search from node 0 finds a cycle only in the group of node 0. It never looks at a node in another group. In the example, the search reaches nodes 0 and 1, so reached is 2 and n is 4. Nodes 2 and 3 are in a separate group. return True accepts this graph, which is a forest and not one tree.
Example: n = 4, edges = [[0, 1], [2, 3]]
Mistake: returns TrueFix: returns False
Gotcha 5: Using the parent check on a directed graph
Mistake
```
has_cycle_undirected(4, [[0, 1], [0, 2], [1, 3], [2, 3]])
```
Fix
```
has_cycle_directed(4, [[0, 1], [0, 2], [1, 3], [2, 3]])
```
What happens: The template stores every edge at both of its ends, so it ignores the direction of each arrow. The arrows 0 -> 1, 0 -> 2, 1 -> 3 and 2 -> 3 give two routes from node 0 to node 3. These two routes are not a directed cycle, because no arrow leads back to node 0. Without the directions, the same four edges form the cycle 0, 1, 3, 2. So the template returns True and the directed answer is False. A directed graph needs a state for a node that is on the current path, and a seen flag with a parent cannot give it. See Cycle Detection in a Directed Graph (DFS Three-Color).
Example: n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3]] as one-way arrows
Mistake: returns TrueFix: returns False

Not this one if…

The edges are one-way arrows and you must find a loop that follows the arrows, as in Course Schedule (LC 207). The parent check reports a node reached by two routes as a cycle, but in a directed graph two routes to one node are not a cycle. See Cycle Detection
You must split the nodes into two groups so that every edge joins different groups, as in Is Graph Bipartite? (LC 785). Only a cycle with an odd number of edges breaks that split, but this card reports a cycle of any length. See Bipartite Check
The edges arrive one at a time and the answer is needed after every edge, as in Number of Islands II (LC 305). Searching the whole graph again after each edge repeats the same work. See Union-Find

Deep Dive

Why the edge back to the parent is not a cycle

An undirected edge joins two nodes in both directions. The code stores it twice: adj[u] holds v, and adj[v] holds u.

Suppose the search goes from u to v. When the search pops v, it scans adj[v], and that list holds u. This is the same edge, walked the other way. It is not a second route to u.

This is why each stack entry carries its parent. The line if v == parent: continue skips exactly the edge the search just used.

Why any other edge to a seen node is a cycle

One trace: the edge 2-3 closes the cycle

The board runs validTree on LeetCode's Example 2: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]].

At that moment reached is 5, so the nodes are all connected. Connection alone does not make a tree. A tree has no cycle, and this graph has one.

A tree also needs one group, and the cost

60-Second Pitch

Common Questions

Why compare with the parent only, and not with every node that is already seen?: Only the parent is certain to be seen because of the edge the search just used. Every other seen node was reached by another route. If a different seen node shows up in adj[u], then u has an edge that is not part of the forest, and that edge closes a cycle. So the parent is the single seen node that is allowed.
Does this work when the same edge appears twice?: Yes, as long as adj is a list. With edges = [[0, 1], [0, 1]], adj[0] is [1, 1]. The first copy reaches node 1. The second copy finds node 1 seen and not the parent of node 0, so the function reports a cycle of two nodes. A set would store node 1 once and lose the cycle.
Can you use BFS in place of DFS?: Yes. The proof needs only that each node is marked once, when it is first reached, together with the node it came from. A queue does that too. Shortest Cycle in a Graph (LC 2608) uses BFS for this reason, and it reads the cycle length from the dist values of the two nodes.
How is this different from Cycle Detection in a Directed Graph (DFS Three-Color)?: In a directed graph, two routes to one node do not make a cycle. The arrows must lead back to a node on the current path. The directed card therefore keeps a state for a node that is on the current path. The parent check only works for undirected edges, where two routes always close a loop.
What are the cost, and when would you use union-find instead?: The search takes O(V + E) time and O(V + E) space. Use union-find when the edges arrive one at a time and you need the answer after each new edge, as in Number of Islands II (LC 305). Union-find answers each new edge in nearly constant time, while this search needs the whole graph first.

SWE Reasoning

Spot it

The statement asks whether an undirected graph is a tree, has a cycle, or which edge closes a loop.
A tree means two things: no cycle, and all nodes in one connected group. Say both parts out loud.
The graph is given as a list of edges, and the whole list is known before the answer is needed.
A cycle in a grid, where each cell is a node, uses the same check with a parent cell.
If the edges have directions, this is a different card.

The invariant, step by step

adj stores every edge at both of its ends. seen[0] is True, reached is 1, and stack holds (0, -1).
Each pop returns (u, parent). The scan of u looks at every neighbour v.
If v == parent, the edge is the one the search used to reach u. Skip it.
If seen[v] is True and v is not the parent, u and v are already linked by another route. Return False.
Otherwise v is new. Mark it seen, add 1 to reached, and push (v, u).
When the stack is empty, there is no cycle. The graph is a tree only if reached == n.

Traps

Starting reached at 0. Node 0 is marked seen before the loop, so it counts as reached. With reached = 0, Example 1 ends with reached = 4 and returns False for a tree.
Trusting the edge count. len(edges) == n - 1 does not rule out a cycle. The triangle [[0, 1], [1, 2], [2, 0]] with n = 4 has 3 edges and still has a cycle.
Recursion on a long path. A recursive search on a path of 2000 nodes needs about 2000 nested calls, and Python's default limit is 1000, so it raises a RecursionError. The explicit stack has no such limit.
One node. n = 1 and edges = [] is a tree. The loop does not run, and reached == n is 1 == 1, so the answer is True.

Practice

Canonical LeetCode:Graph Valid Tree (LC 261)Redundant Connection (LC 684)Detect Cycles in 2D Grid (LC 1559)Shortest Cycle in a Graph (LC 2608)