LeetCode Patterns ·

🎯 Graph Cycle Detection

1️⃣ Core Framework

When discussing Graph Cycle Detection, I frame it as:

What cycle detection means
Cycle in undirected graph
Cycle in directed graph
DFS with parent tracking
DFS with recursion state
Topological sort cycle detection
Union Find for undirected cycles
Grid cycle detection
Course Schedule pattern
Senior-level explanation

2️⃣ What Problem Are We Solving?

Graph cycle detection asks:

Does this graph contain a cycle?

A cycle means:

We can start from a node,
follow edges,
and eventually return to a previously visited node.

It is commonly used for:

Course schedule
Dependency validation
Detecting circular dependencies
Undirected graph cycle detection
Directed graph cycle detection
Union Find cycle detection
Topological sort validation
Build system dependency graph
Package dependency graph
Deadlock detection
Grid cycle detection
Redundant connection

The core idea is:

Cycle detection depends on graph direction.
Undirected graph and directed graph use different logic.

👉 Interview Answer

Graph cycle detection is the process of determining whether a graph contains a path that returns to a previously visited node.

In an undirected graph, we usually use DFS with parent tracking or Union Find.

In a directed graph, we usually use DFS with recursion state or topological sort.

The most important first step is to identify whether the graph is directed or undirected.

3️⃣ Cycle in Undirected Graph

Definition

In an undirected graph, a cycle exists if we can revisit a visited node that is not the immediate parent.

Example:

0 -- 1
|    |
3 -- 2

This graph has a cycle:

0 -> 1 -> 2 -> 3 -> 0

Key Rule

During DFS:

If neighbor is visited
and neighbor is not parent,
then cycle exists.

Why Parent Matters

In an undirected graph, every edge appears in both directions.

If we go:

0 -> 1

Then from 1, we see 0 again.

That does not mean cycle. It is just the edge back to parent.

👉 Interview Answer

In an undirected graph, a cycle exists if DFS reaches a previously visited node that is not the parent of the current node.

The parent check is necessary because every undirected edge appears in both directions.

Seeing the parent again is normal, but seeing another visited node means there is a cycle.

4️⃣ Undirected Graph DFS Template

Code

from collections import defaultdict

def has_cycle_undirected(n, edges):
    graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()

    def dfs(node, parent):
        visited.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True

        return False

    for node in range(n):
        if node not in visited:
            if dfs(node, -1):
                return True

    return False

Why Loop All Nodes?

The graph may be disconnected.

So we need to start DFS from every unvisited node.

👉 Interview Answer

For undirected graph cycle detection, I build an adjacency list and run DFS.

During DFS, I pass the parent node.

If I see a visited neighbor that is not the parent, then there is a cycle.

I also loop through all nodes because the graph may be disconnected.

5️⃣ Cycle in Directed Graph

Definition

In a directed graph, a cycle exists if we can follow directed edges and return to a node currently in the recursion path.

Example:

0 -> 1 -> 2
     ↑    |
     |____|

This has a cycle:

1 -> 2 -> 1

Key Difference

In directed graphs, parent tracking is not enough.

We need to know whether a node is:

currently being visited
already fully processed
never visited

Three States

= unvisited
= visiting
= visited

If DFS reaches a visiting node:

cycle exists

👉 Interview Answer

In a directed graph, cycle detection requires tracking the current recursion path.

I usually use three states: unvisited, visiting, and visited.

If DFS reaches a node that is already in the visiting state, that means we found a back edge, so a directed cycle exists.

6️⃣ Directed Graph DFS Template

Code

from collections import defaultdict

def has_cycle_directed(n, edges):
    graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)

    state = [0] * n

    def dfs(node):
        if state[node] == 1:
            return True

        if state[node] == 2:
            return False

        state[node] = 1

        for neighbor in graph[node]:
            if dfs(neighbor):
                return True

        state[node] = 2
        return False

    for node in range(n):
        if state[node] == 0:
            if dfs(node):
                return True

    return False

State Meaning

never visited
currently in recursion stack
fully processed

👉 Interview Answer

For directed graph cycle detection, I use DFS with three states.

When entering a node, I mark it as visiting.

If I reach another visiting node, I found a cycle.

After all neighbors are processed, I mark the node as fully visited.

7️⃣ Course Schedule

Problem

There are numCourses courses and prerequisites.

Each prerequisite:

[a, b]

means:

To take course a,
you must first take course b.

Return whether it is possible to finish all courses.

Graph Model

Create edge:

b -> a

If the dependency graph has a cycle:

impossible

Code: DFS State

from collections import defaultdict

def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)

    for course, prereq in prerequisites:
        graph[prereq].append(course)

    state = [0] * num_courses

    def dfs(course):
        if state[course] == 1:
            return False

        if state[course] == 2:
            return True

        state[course] = 1

        for next_course in graph[course]:
            if not dfs(next_course):
                return False

        state[course] = 2
        return True

    for course in range(num_courses):
        if state[course] == 0:
            if not dfs(course):
                return False

    return True

👉 Interview Answer

Course Schedule is a directed graph cycle detection problem.

Each prerequisite creates a directed edge from prerequisite to course.

If there is a cycle, then some courses depend on each other circularly, so it is impossible to finish all courses.

I can detect this using DFS with visiting and visited states.

8️⃣ Course Schedule II

Problem

Return one valid order to finish all courses.

If impossible, return empty list.

Topological Sort

This is also cycle detection.

If we cannot process all nodes, there is a cycle.

Code: Kahn’s Algorithm

from collections import defaultdict, deque

def find_order(num_courses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque()

    for course in range(num_courses):
        if indegree[course] == 0:
            queue.append(course)

    order = []

    while queue:
        course = queue.popleft()
        order.append(course)

        for next_course in graph[course]:
            indegree[next_course] -= 1

            if indegree[next_course] == 0:
                queue.append(next_course)

    if len(order) != num_courses:
        return []

    return order

👉 Interview Answer

Course Schedule II can be solved with topological sort.

I start with courses that have indegree zero.

Each time I process a course, I reduce the indegree of dependent courses.

If I cannot process all courses, then some courses are stuck in a cycle, so no valid ordering exists.

9️⃣ Topological Sort Cycle Detection

Kahn’s Algorithm

For a directed graph:

Compute indegree for every node.
Push all nodes with indegree 0 into queue.
Process nodes and reduce neighbors' indegrees.

If processed count is less than total nodes:

cycle exists

Code

from collections import defaultdict, deque

def has_cycle_topological(n, edges):
    graph = defaultdict(list)
    indegree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque()

    for node in range(n):
        if indegree[node] == 0:
            queue.append(node)

    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1

        for neighbor in graph[node]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return processed != n

👉 Interview Answer

Topological sort can detect cycles in a directed graph.

If a graph has no cycle, we can repeatedly remove nodes with indegree zero.

If some nodes remain unprocessed, they must be part of or blocked by a cycle.

Therefore, processed count less than n means a cycle exists.

🔟 DFS State vs Topological Sort

DFS State

Good for:

detecting directed cycles
recursive dependency validation
simple cycle existence
DFS-style reasoning

Topological Sort

Good for:

detecting cycles
returning valid order
course schedule
build order
dependency resolution

Comparison

Pattern	Best For
DFS State	Detect directed cycle
Topological Sort	Detect cycle and return order
Union Find	Undirected cycle detection
DFS Parent	Undirected cycle detection

👉 Interview Answer

DFS with states and topological sort can both detect cycles in directed graphs.

DFS state is direct and good for detecting whether a cycle exists.

Topological sort is better when the problem also asks for a valid ordering.

If topological sort cannot process all nodes, the graph has a cycle.

1️⃣1️⃣ Union Find for Undirected Cycle

When to Use Union Find

Use Union Find when:

undirected graph
edges are processed one by one
need to detect redundant edge
need connected component merging

Key Idea

For each edge (u, v):

if find(u) == find(v):
    cycle exists
else:
    union(u, v)

Code

def has_cycle_union_find(n, edges):
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])

        return parent[x]

    def union(a, b):
        root_a = find(a)
        root_b = find(b)

        if root_a == root_b:
            return False

        if rank[root_a] < rank[root_b]:
            parent[root_a] = root_b
        elif rank[root_a] > rank[root_b]:
            parent[root_b] = root_a
        else:
            parent[root_b] = root_a
            rank[root_a] += 1

        return True

    for u, v in edges:
        if not union(u, v):
            return True

    return False

👉 Interview Answer

In an undirected graph, Union Find can detect cycles while processing edges.

If an edge connects two nodes that already have the same root, then those nodes are already connected.

Adding that edge would create a cycle.

Otherwise, I union the two components.

1️⃣2️⃣ Redundant Connection

Problem

A graph started as a tree, then one extra edge was added.

Return the edge that creates a cycle.

Union Find Approach

Process edges in order.

The first edge whose endpoints are already connected is the answer.

Code

def find_redundant_connection(edges):
    n = len(edges)
    parent = list(range(n + 1))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])

        return parent[x]

    def union(a, b):
        root_a = find(a)
        root_b = find(b)

        if root_a == root_b:
            return False

        parent[root_b] = root_a
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]

    return []

👉 Interview Answer

Redundant Connection is an undirected cycle detection problem.

I process edges one by one using Union Find.

If an edge connects two nodes already in the same component, that edge creates a cycle, so I return it.

1️⃣3️⃣ Directed Cycle With Recursion Stack

Alternative Template

Instead of three states, we can use:

visited
recursion_stack

Code

from collections import defaultdict

def has_cycle_directed_stack(n, edges):
    graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)

    visited = set()
    recursion_stack = set()

    def dfs(node):
        visited.add(node)
        recursion_stack.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in recursion_stack:
                return True

        recursion_stack.remove(node)
        return False

    for node in range(n):
        if node not in visited:
            if dfs(node):
                return True

    return False

👉 Interview Answer

Another way to detect cycles in a directed graph is to maintain a recursion stack.

If DFS reaches a node already in the current recursion stack, then there is a back edge, so a cycle exists.

This is equivalent to the three-state DFS approach.

1️⃣4️⃣ Cycle Detection in Grid

Problem

Given a grid of characters, determine whether there is a cycle formed by cells with the same value.

Model

Each cell is a node.

Edges connect adjacent cells with the same character.

Use DFS with parent tracking.

Code

def contains_cycle(grid):
    rows = len(grid)
    cols = len(grid[0])
    visited = set()

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def dfs(r, c, parent_r, parent_c, char):
        visited.add((r, c))

        for dr, dc in directions:
            nr = r + dr
            nc = c + dc

            if not (0 <= nr < rows and 0 <= nc < cols):
                continue

            if grid[nr][nc] != char:
                continue

            if (nr, nc) == (parent_r, parent_c):
                continue

            if (nr, nc) in visited:
                return True

            if dfs(nr, nc, r, c, char):
                return True

        return False

    for r in range(rows):
        for c in range(cols):
            if (r, c) not in visited:
                if dfs(r, c, -1, -1, grid[r][c]):
                    return True

    return False

👉 Interview Answer

Grid cycle detection can be modeled as undirected graph cycle detection.

Each cell is a node, and adjacent cells with the same character are connected.

During DFS, if I reach a visited cell that is not the parent, then a cycle exists.

1️⃣5️⃣ Detect Cycle in Linked List

Although not a graph adjacency-list problem, linked list cycle detection is also cycle detection.

Use fast and slow pointers.

Code

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

👉 Interview Answer

Linked List Cycle is a special cycle detection problem.

Instead of DFS, I use fast and slow pointers.

If there is a cycle, the fast pointer will eventually meet the slow pointer.

If fast reaches null, there is no cycle.

1️⃣6️⃣ Cycle Detection in Functional Graph

Functional Graph

A functional graph is a graph where each node has exactly one outgoing edge.

Example:

next[i] = j

This appears in:

array jumping
duplicate number
linked list-like graph

Floyd’s Cycle Detection

Use:

slow moves 1 step
fast moves 2 steps

Code

def has_cycle_functional(next_node, start):
    slow = start
    fast = start

    while True:
        slow = next_node[slow]
        fast = next_node[next_node[fast]]

        if slow == fast:
            return True

👉 Interview Answer

In a functional graph, each node has one outgoing edge, so following edges behaves like a linked list with possible cycle.

Floyd’s fast and slow pointer technique can detect the cycle efficiently.

This is useful in problems like finding duplicate number.

1️⃣7️⃣ Find Duplicate Number

Problem

Given an array nums with n + 1 integers in range 1 to n, find the duplicate number.

Functional Graph Model

Treat each index as a node:

i -> nums[i]

Because values are in range 1 to n, there must be a cycle.

The duplicate number is the cycle entry.

Code

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast:
            break

    slow = nums[0]

    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

👉 Interview Answer

Find Duplicate Number can be modeled as cycle detection in a functional graph.

Each index points to nums[index].

Because there are n + 1 values in range 1 to n, two indices point into the same path, creating a cycle.

The duplicate number is the cycle entry, which can be found using Floyd’s algorithm.

1️⃣8️⃣ Cycle Detection in Dependency Graphs

Real-World Examples

Directed cycle detection is common in dependency systems:

Course prerequisites
Build systems
Package managers
Workflow dependencies
Task scheduling
Database migration ordering

Why Cycle Is Bad

A cycle means:

A depends on B
B depends on C
C depends on A

No task can start first.

Best Pattern

Use:

DFS state
or
topological sort

👉 Interview Answer

In dependency graphs, a directed cycle means circular dependency.

For example, A depends on B, B depends on C, and C depends on A.

This makes it impossible to produce a valid execution order.

I usually detect this with DFS states or topological sort.

1️⃣9️⃣ Undirected vs Directed Cycle Detection

Undirected Graph

Use:

DFS with parent
Union Find

Cycle means:

visited neighbor that is not parent

Directed Graph

Use:

DFS with recursion state
Topological sort

Cycle means:

back edge to a node currently in recursion stack

Comparison

Graph Type	Best Pattern	Key Idea
Undirected	DFS + parent	visited neighbor not parent
Undirected	Union Find	edge connects same component
Directed	DFS states	reach visiting node
Directed	Topological sort	cannot process all nodes

👉 Interview Answer

Undirected and directed cycle detection are different.

In an undirected graph, seeing a visited neighbor is only a cycle if that neighbor is not the parent.

In a directed graph, a cycle exists when DFS reaches a node currently in the recursion path.

For directed graphs, parent tracking alone is not enough.

2️⃣0️⃣ Complexity Analysis

DFS Cycle Detection

For both directed and undirected graphs:

Time: O(V + E)
Space: O(V + E)

Adjacency list stores edges.

Visited or state arrays store node states.

Topological Sort

Time: O(V + E)
Space: O(V + E)

Union Find

For E edges and V nodes:

Time: O(E α(V))
Space: O(V)

In practice:

almost O(E)

👉 Interview Answer

DFS-based cycle detection runs in O(V + E), because each node and edge is processed once.

Topological sort also runs in O(V + E).

Union Find runs in almost linear time, specifically O(E α(V)), where α is the inverse Ackermann function.

2️⃣1️⃣ Common Edge Cases

Disconnected Graph

Need to start DFS from every unvisited node.

Self Loop

u -> u

Usually this is a cycle.

Parallel Edges

In undirected graphs, duplicate edges may create a cycle depending on problem definition.

One Node

A single node without self-loop has no cycle.

Directed Acyclic Graph

Should return no cycle.

1-Indexed Nodes

Many graph problems use:

1 to n

Need array size:

n + 1

👉 Interview Answer

Common cycle detection edge cases include disconnected graphs, self-loops, parallel edges, one-node graphs, directed acyclic graphs, and 1-indexed node labels.

I make sure to run DFS from every unvisited node, not just node zero.

2️⃣2️⃣ Common Mistakes

Mistake 1: Using Directed Logic for Undirected Graph

Directed recursion-state logic is not the same as undirected parent tracking.

Mistake 2: Forgetting Parent in Undirected DFS

Without parent, the edge back to previous node looks like a false cycle.

Mistake 3: Using Parent Tracking for Directed Graph

Parent tracking alone does not detect all directed cycles correctly.

Mistake 4: Not Handling Disconnected Graphs

Starting DFS only from node 0 may miss cycles elsewhere.

Mistake 5: Forgetting to Mark Node as Fully Visited

In directed DFS, after processing neighbors:

state[node] = 2

Mistake 6: Wrong Edge Direction in Course Schedule

For prerequisite [course, prereq], edge should usually be:

prereq -> course

👉 Interview Answer

Common cycle detection mistakes include mixing directed and undirected logic, forgetting the parent check in undirected DFS, using parent tracking for directed graphs, missing disconnected components, forgetting to mark nodes as fully visited, and reversing prerequisite edge directions.

2️⃣3️⃣ When Graph Cycle Detection Applies

Good Fit

Use cycle detection when the problem asks for:

detect circular dependency
can finish all tasks
valid dependency order
redundant connection
whether graph is a tree
deadlock possibility
package dependency conflict
build order validation

Problem Signals

Look for words like:

cycle
circular
dependency
prerequisite
can finish
valid order
tree
redundant connection
deadlock
loop

👉 Interview Answer

I consider cycle detection when the problem involves dependency validation, circular relationships, checking whether tasks can be completed, determining whether a graph is a tree, or finding a redundant connection.

The first question is whether the graph is directed or undirected.

2️⃣4️⃣ When Graph Cycle Detection Does Not Apply

Not Good Fit

Cycle detection may not be enough when:

need shortest path
need minimum spanning tree
need all possible paths
need connected components only
need strongly connected components
need max flow

Better Alternatives

Problem Type	Better Pattern
Shortest path	BFS / Dijkstra
Minimum total connection cost	MST / Kruskal / Prim
All valid paths	Backtracking / DFS
Connected components	DFS / BFS / Union Find
Strongly connected components	Tarjan / Kosaraju
Dependency ordering	Topological Sort
Dynamic connectivity	Union Find

👉 Interview Answer

Cycle detection only answers whether a cycle exists.

If the problem asks for shortest path, minimum spanning tree, all paths, or strongly connected components, then we need a different graph algorithm.

The key is to identify whether the cycle itself is the main constraint.

2️⃣5️⃣ Standard Templates

Undirected DFS Cycle Template

def has_cycle_undirected(n, graph):
    visited = set()

    def dfs(node, parent):
        visited.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True

        return False

    for node in range(n):
        if node not in visited:
            if dfs(node, -1):
                return True

    return False

Directed DFS State Template

def has_cycle_directed(n, graph):
    state = [0] * n

    def dfs(node):
        if state[node] == 1:
            return True

        if state[node] == 2:
            return False

        state[node] = 1

        for neighbor in graph[node]:
            if dfs(neighbor):
                return True

        state[node] = 2
        return False

    for node in range(n):
        if state[node] == 0:
            if dfs(node):
                return True

    return False

Topological Sort Cycle Template

from collections import deque

def has_cycle_topological(n, graph, indegree):
    queue = deque()

    for node in range(n):
        if indegree[node] == 0:
            queue.append(node)

    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1

        for neighbor in graph[node]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return processed != n

Union Find Cycle Template

def has_cycle_union_find(n, edges):
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])

        return parent[x]

    def union(a, b):
        root_a = find(a)
        root_b = find(b)

        if root_a == root_b:
            return False

        parent[root_b] = root_a
        return True

    for u, v in edges:
        if not union(u, v):
            return True

    return False

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Graph cycle detection determines whether a graph contains a path that eventually returns to a previously visited node.

The most important first distinction is whether the graph is undirected or directed, because the detection logic is different.

In an undirected graph, a cycle exists if DFS reaches a visited neighbor that is not the parent. The parent check is necessary because every undirected edge appears in both directions. Seeing the parent again is normal, but seeing another visited node means there is a cycle.

For undirected graphs, Union Find is another strong approach. When processing an edge, if the two endpoints already belong to the same connected component, then adding that edge creates a cycle. Otherwise, we union the two components.

In a directed graph, parent tracking is not enough. We need to know whether a node is currently in the recursion path. A common DFS approach uses three states: unvisited, visiting, and visited. If DFS reaches a visiting node, that is a back edge, so a directed cycle exists.

Topological sort is another way to detect cycles in directed graphs. If the graph has no cycle, we should be able to process all nodes by repeatedly removing nodes with indegree zero. If some nodes remain unprocessed, they are part of or blocked by a cycle.

Course Schedule is a classic directed cycle detection problem. Each prerequisite creates a dependency edge. If there is a cycle, courses depend on each other circularly, so it is impossible to finish all courses.

Grid cycle detection can often be modeled as undirected graph cycle detection, where each cell is a node and adjacent same-character cells are edges.

The complexity of DFS and topological sort cycle detection is O(V + E). Union Find is almost linear, O(E α(V)).

At a senior level, I would explain: whether the graph is directed or undirected, what a cycle means in that graph, why undirected graphs need parent tracking, why directed graphs need recursion state, when topological sort is more useful, when Union Find is simpler, and how edge cases like disconnected graphs and self-loops are handled.

⭐ Final Insight

Graph Cycle Detection 的核心不是“看到 visited 就 return true”。

它的核心是先判断 graph type：

undirected graph 需要 parent tracking， directed graph 需要 recursion state， dependency graph 可以用 topological sort， edge-by-edge undirected graph 可以用 Union Find。

Senior-level 的重点是：

cycle 在当前问题中代表什么， graph 是 directed 还是 undirected， visited 的含义是什么， parent 为什么只适用于 undirected graph， visiting state 为什么能检测 directed back edge， topological sort 为什么能发现 circular dependency，以及 disconnected graph 为什么必须全部遍历。

能讲清楚这些， Graph Cycle Detection 就是一类处理 circular dependency、redundant connection、valid ordering 和 graph validity 的核心模式。

中文部分

🎯 Graph Cycle Detection

1️⃣ 核心框架

讨论 Graph Cycle Detection 时，我通常从：

Cycle detection 是什么
Cycle in undirected graph
Cycle in directed graph
DFS with parent tracking
DFS with recursion state
Topological sort cycle detection
Union Find for undirected cycles
Grid cycle detection
Course Schedule pattern
高级工程师解释方式

2️⃣ 要解决什么问题？

Graph cycle detection 问的是：

这个 graph 中是否存在 cycle？

Cycle 表示：

从某个 node 出发，
沿着 edges 走，
最终可以回到之前访问过的 node。

它常用于：

Course schedule
Dependency validation
Detecting circular dependencies
Undirected graph cycle detection
Directed graph cycle detection
Union Find cycle detection
Topological sort validation
Build system dependency graph
Package dependency graph
Deadlock detection
Grid cycle detection
Redundant connection

核心思想是：

Cycle detection 取决于 graph 是否有方向。
Undirected graph 和 directed graph 的判断逻辑不同。

👉 面试回答

Graph cycle detection 是判断 graph 中是否存在一条 path，可以回到之前访问过的 node。

在 undirected graph 中，通常使用 DFS with parent tracking 或 Union Find。

在 directed graph 中，通常使用 DFS with recursion state 或 topological sort。

最重要的第一步是判断 graph 是 directed 还是 undirected。

3️⃣ Cycle in Undirected Graph

Definition

在 undirected graph 中，如果 DFS 访问到了一个已经 visited 的 node，并且这个 node 不是当前 node 的 parent，说明存在 cycle。

Example:

0 -- 1
|    |
3 -- 2

这个 graph 有 cycle：

0 -> 1 -> 2 -> 3 -> 0

Key Rule

DFS 过程中：

如果 neighbor 已经 visited
并且 neighbor 不是 parent
那么存在 cycle

Why Parent Matters

在 undirected graph 中，每条 edge 都可以双向走。

如果我们走：

0 -> 1

那么从 1 又能看到 0。

这不代表 cycle。这只是回到了 parent。

👉 面试回答

在 undirected graph 中，如果 DFS 访问到一个已经 visited 的 neighbor，并且这个 neighbor 不是 parent，那么存在 cycle。

parent check 很重要，因为 undirected edge 会双向出现。

看到 parent 是正常的，但看到其他 visited node 才说明 cycle。

4️⃣ Undirected Graph DFS Template

Code

from collections import defaultdict

def has_cycle_undirected(n, edges):
    graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()

    def dfs(node, parent):
        visited.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True

        return False

    for node in range(n):
        if node not in visited:
            if dfs(node, -1):
                return True

    return False

Why Loop All Nodes?

Graph 可能是 disconnected。

所以需要从每个 unvisited node 开始 DFS。

👉 面试回答

对 undirected graph cycle detection，我会先建 adjacency list，然后 DFS。

DFS 时传入 parent node。

如果看到 visited neighbor 且不是 parent，就说明有 cycle。

还要遍历所有 nodes，因为 graph 可能不是 connected。

5️⃣ Cycle in Directed Graph

Definition

在 directed graph 中，如果我们沿着 directed edges 能回到当前 recursion path 中的 node，就存在 cycle。

Example:

0 -> 1 -> 2
     ↑    |
     |____|

这个 graph 有 cycle：

1 -> 2 -> 1

Key Difference

Directed graph 中， parent tracking 不够。

我们需要知道一个 node 是：

currently being visited
already fully processed
never visited

Three States

= unvisited
= visiting
= visited

如果 DFS 到达 visiting node：

cycle exists

👉 面试回答

在 directed graph 中， cycle detection 需要追踪当前 recursion path。

我通常使用三个状态： unvisited、visiting、visited。

如果 DFS 到达一个已经处于 visiting 状态的 node，说明找到 back edge，因此存在 directed cycle。

6️⃣ Directed Graph DFS Template

Code

from collections import defaultdict

def has_cycle_directed(n, edges):
    graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)

    state = [0] * n

    def dfs(node):
        if state[node] == 1:
            return True

        if state[node] == 2:
            return False

        state[node] = 1

        for neighbor in graph[node]:
            if dfs(neighbor):
                return True

        state[node] = 2
        return False

    for node in range(n):
        if state[node] == 0:
            if dfs(node):
                return True

    return False

State Meaning

never visited
currently in recursion stack
fully processed

👉 面试回答

对 directed graph cycle detection，我使用 DFS with three states。

进入 node 时，标记为 visiting。

如果访问到另一个 visiting node，说明找到了 cycle。

当所有 neighbors 都处理完后，把 node 标记为 fully visited。

7️⃣ Course Schedule

Problem

有 numCourses 门课和 prerequisites。

每个 prerequisite：

[a, b]

表示：

要上 course a，
必须先上 course b。

判断是否可以完成所有课程。

Graph Model

创建 edge：

b -> a

如果 dependency graph 中有 cycle：

impossible

Code: DFS State

from collections import defaultdict

def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)

    for course, prereq in prerequisites:
        graph[prereq].append(course)

    state = [0] * num_courses

    def dfs(course):
        if state[course] == 1:
            return False

        if state[course] == 2:
            return True

        state[course] = 1

        for next_course in graph[course]:
            if not dfs(next_course):
                return False

        state[course] = 2
        return True

    for course in range(num_courses):
        if state[course] == 0:
            if not dfs(course):
                return False

    return True

👉 面试回答

Course Schedule 是一个 directed graph cycle detection problem。

每个 prerequisite 创建一条从 prerequisite 到 course 的 directed edge。

如果存在 cycle，说明一些 courses 互相依赖，因此无法完成所有课程。

可以用 DFS with visiting/visited states 来检测。

8️⃣ Course Schedule II

Problem

返回完成所有 courses 的一个 valid order。

如果不可能，返回 empty list。

Topological Sort

这也是 cycle detection。

如果无法处理所有 nodes，说明有 cycle。

Code: Kahn’s Algorithm

from collections import defaultdict, deque

def find_order(num_courses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque()

    for course in range(num_courses):
        if indegree[course] == 0:
            queue.append(course)

    order = []

    while queue:
        course = queue.popleft()
        order.append(course)

        for next_course in graph[course]:
            indegree[next_course] -= 1

            if indegree[next_course] == 0:
                queue.append(next_course)

    if len(order) != num_courses:
        return []

    return order

👉 面试回答

Course Schedule II 可以用 topological sort。

我从 indegree 为 0 的 courses 开始。

每处理一门 course，就减少依赖它的 courses 的 indegree。

如果最后不能处理所有 courses，说明有 courses 卡在 cycle 中，因此不存在 valid ordering。

9️⃣ Topological Sort Cycle Detection

Kahn’s Algorithm

对于 directed graph：

计算每个 node 的 indegree。
把所有 indegree 为 0 的 nodes 放入 queue。
处理 nodes 并减少 neighbors 的 indegree。

如果 processed count 小于 total nodes：

cycle exists

Code

from collections import defaultdict, deque

def has_cycle_topological(n, edges):
    graph = defaultdict(list)
    indegree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque()

    for node in range(n):
        if indegree[node] == 0:
            queue.append(node)

    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1

        for neighbor in graph[node]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return processed != n

👉 面试回答

Topological sort 可以检测 directed graph 中的 cycle。

如果 graph 没有 cycle，我们应该可以不断移除 indegree 为 0 的 nodes。

如果有 nodes 无法被处理，它们一定在 cycle 中，或者被 cycle 阻塞。

因此 processed count 小于 n，就说明存在 cycle。

🔟 DFS State vs Topological Sort

DFS State

适合：

detecting directed cycles
recursive dependency validation
simple cycle existence
DFS-style reasoning

Topological Sort

适合：

detecting cycles
returning valid order
course schedule
build order
dependency resolution

Comparison

Pattern	Best For
DFS State	Detect directed cycle
Topological Sort	Detect cycle and return order
Union Find	Undirected cycle detection
DFS Parent	Undirected cycle detection

👉 面试回答

DFS with states 和 topological sort 都可以检测 directed graph cycle。

DFS state 直接适合判断是否存在 cycle。

Topological sort 更适合当题目还需要返回 valid order 的场景。

如果 topological sort 不能处理所有 nodes，就说明 graph 中存在 cycle。

1️⃣1️⃣ Union Find for Undirected Cycle

When to Use Union Find

当满足：

undirected graph
edges are processed one by one
need to detect redundant edge
need connected component merging

可以使用 Union Find。

Key Idea

对每条 edge (u, v)：

if find(u) == find(v):
    cycle exists
else:
    union(u, v)

Code

def has_cycle_union_find(n, edges):
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])

        return parent[x]

    def union(a, b):
        root_a = find(a)
        root_b = find(b)

        if root_a == root_b:
            return False

        if rank[root_a] < rank[root_b]:
            parent[root_a] = root_b
        elif rank[root_a] > rank[root_b]:
            parent[root_b] = root_a
        else:
            parent[root_b] = root_a
            rank[root_a] += 1

        return True

    for u, v in edges:
        if not union(u, v):
            return True

    return False

👉 面试回答

在 undirected graph 中， Union Find 可以在处理 edges 的过程中检测 cycle。

如果一条 edge 连接的两个 nodes 已经有相同 root，说明它们已经 connected。

再加入这条 edge 就会形成 cycle。

否则，就 union 这两个 components。

1️⃣2️⃣ Redundant Connection

Problem

一个 graph 原本是 tree，后来多加了一条 edge。

返回造成 cycle 的 edge。

Union Find Approach

按顺序处理 edges。

第一个 endpoints 已经 connected 的 edge 就是答案。

Code

def find_redundant_connection(edges):
    n = len(edges)
    parent = list(range(n + 1))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])

        return parent[x]

    def union(a, b):
        root_a = find(a)
        root_b = find(b)

        if root_a == root_b:
            return False

        parent[root_b] = root_a
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]

    return []

👉 面试回答

Redundant Connection 是一个 undirected cycle detection problem。

我用 Union Find 按顺序处理每条 edge。

如果某条 edge 连接的两个 nodes 已经属于同一个 component，那么这条 edge 就会造成 cycle，所以返回它。

1️⃣3️⃣ Directed Cycle With Recursion Stack

Alternative Template

除了 three states，也可以使用：

visited
recursion_stack

Code

from collections import defaultdict

def has_cycle_directed_stack(n, edges):
    graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)

    visited = set()
    recursion_stack = set()

    def dfs(node):
        visited.add(node)
        recursion_stack.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in recursion_stack:
                return True

        recursion_stack.remove(node)
        return False

    for node in range(n):
        if node not in visited:
            if dfs(node):
                return True

    return False

👉 面试回答

Directed graph cycle detection 也可以用 recursion stack。

如果 DFS 访问到一个已经在当前 recursion stack 中的 node，说明存在 back edge，因此有 cycle。

这和 three-state DFS 本质上是同一种思路。

1️⃣4️⃣ Cycle Detection in Grid

Problem

给定一个 characters grid，判断是否存在由相同字符 cells 组成的 cycle。

Model

每个 cell 是一个 node。

相邻且 character 相同的 cells 之间有 edge。

使用 DFS with parent tracking。

Code

def contains_cycle(grid):
    rows = len(grid)
    cols = len(grid[0])
    visited = set()

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def dfs(r, c, parent_r, parent_c, char):
        visited.add((r, c))

        for dr, dc in directions:
            nr = r + dr
            nc = c + dc

            if not (0 <= nr < rows and 0 <= nc < cols):
                continue

            if grid[nr][nc] != char:
                continue

            if (nr, nc) == (parent_r, parent_c):
                continue

            if (nr, nc) in visited:
                return True

            if dfs(nr, nc, r, c, char):
                return True

        return False

    for r in range(rows):
        for c in range(cols):
            if (r, c) not in visited:
                if dfs(r, c, -1, -1, grid[r][c]):
                    return True

    return False

👉 面试回答

Grid cycle detection 可以建模成 undirected graph cycle detection。

每个 cell 是 node，相邻且字符相同的 cells 之间有 edge。

DFS 时，如果到达一个 visited cell，并且它不是 parent，说明存在 cycle。

1️⃣5️⃣ Detect Cycle in Linked List

虽然 linked list cycle 不是普通 adjacency-list graph，但它也是 cycle detection。

使用 fast and slow pointers。

Code

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

👉 面试回答

Linked List Cycle 是一种特殊的 cycle detection。

这里不用 DFS，而是使用 fast and slow pointers。

如果存在 cycle， fast pointer 最终会追上 slow pointer。

如果 fast 走到 null，则没有 cycle。

1️⃣6️⃣ Cycle Detection in Functional Graph

Functional Graph

Functional graph 是每个 node 只有一条 outgoing edge 的 graph。

Example:

next[i] = j

它常出现在：

array jumping
duplicate number
linked list-like graph

Floyd’s Cycle Detection

使用：

slow 每次走 1 步
fast 每次走 2 步

Code

def has_cycle_functional(next_node, start):
    slow = start
    fast = start

    while True:
        slow = next_node[slow]
        fast = next_node[next_node[fast]]

        if slow == fast:
            return True

👉 面试回答

在 functional graph 中，每个 node 只有一个 outgoing edge，所以沿着 edges 走很像 linked list。

Floyd fast and slow pointer technique 可以高效检测 cycle。

这常用于 Find Duplicate Number 这类问题。

1️⃣7️⃣ Find Duplicate Number

Problem

给定一个 array nums，包含 n + 1 个整数，每个整数范围是 1 到 n，找出 duplicate number。

Functional Graph Model

把每个 index 看成 node：

i -> nums[i]

因为 values 范围是 1 到 n，一定会形成 cycle。

Duplicate number 是 cycle entry。

Code

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast:
            break

    slow = nums[0]

    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

👉 面试回答

Find Duplicate Number 可以建模为 functional graph cycle detection。

每个 index 指向 nums[index]。

因为有 n + 1 个 values，但 value range 只有 1 到 n，所以一定有两个 indices 进入同一条路径，从而形成 cycle。

duplicate number 就是 cycle entry，可以用 Floyd algorithm 找到。

1️⃣8️⃣ Cycle Detection in Dependency Graphs

Real-World Examples

Directed cycle detection 常见于 dependency systems：

Course prerequisites
Build systems
Package managers
Workflow dependencies
Task scheduling
Database migration ordering

Why Cycle Is Bad

Cycle 表示：

A depends on B
B depends on C
C depends on A

没有一个 task 能先开始。

Best Pattern

使用：

DFS state
or
topological sort

👉 面试回答

在 dependency graph 中， directed cycle 表示 circular dependency。

例如 A depends on B， B depends on C， C depends on A。

这会导致没有任何一个 task 可以作为起点。

我通常使用 DFS states 或 topological sort 来检测。

1️⃣9️⃣ Undirected vs Directed Cycle Detection

Undirected Graph

使用：

DFS with parent
Union Find

Cycle 意味着：

visited neighbor that is not parent

Directed Graph

使用：

DFS with recursion state
Topological sort

Cycle 意味着：

back edge to a node currently in recursion stack

Comparison

Graph Type	Best Pattern	Key Idea
Undirected	DFS + parent	visited neighbor not parent
Undirected	Union Find	edge connects same component
Directed	DFS states	reach visiting node
Directed	Topological sort	cannot process all nodes

👉 面试回答

Undirected 和 directed cycle detection 是不同问题。

在 undirected graph 中，看到 visited neighbor 只有在它不是 parent 时，才说明 cycle。

在 directed graph 中， cycle 是 DFS 到达当前 recursion path 中的 node。

对 directed graph， parent tracking alone 不够。

2️⃣0️⃣ Complexity Analysis

DFS Cycle Detection

对于 directed 和 undirected graphs：

Time: O(V + E)
Space: O(V + E)

Adjacency list 存 edges。

Visited 或 state arrays 存 node states。

Topological Sort

Time: O(V + E)
Space: O(V + E)

Union Find

对于 E 条 edges 和 V 个 nodes：

Time: O(E α(V))
Space: O(V)

实践中：

almost O(E)

👉 面试回答

DFS-based cycle detection 是 O(V + E)，因为每个 node 和 edge 都只处理一次。

Topological sort 也是 O(V + E)。

Union Find 接近线性时间，更严格地说是 O(E α(V))，其中 α 是 inverse Ackermann function。

2️⃣1️⃣ 常见 Edge Cases

Disconnected Graph

需要从每个 unvisited node 开始 DFS。

Self Loop

u -> u

通常就是 cycle。

Parallel Edges

在 undirected graph 中， duplicate edges 根据题目定义可能形成 cycle。

One Node

一个没有 self-loop 的 single node 没有 cycle。

Directed Acyclic Graph

应该返回 no cycle。

1-Indexed Nodes

很多 graph problems 使用：

1 to n

需要 array size：

n + 1

👉 面试回答

Cycle detection 常见 edge cases 包括 disconnected graph、 self-loop、 parallel edges、 one-node graph、 directed acyclic graph，以及 1-indexed nodes。

我会确保从每个 unvisited node 开始 DFS，而不是只从 node 0 开始。

2️⃣2️⃣ 常见错误

Mistake 1: Directed 和 Undirected Logic 混用

Directed recursion-state logic 和 undirected parent tracking 不是一回事。

Mistake 2: Undirected DFS 忘记 Parent

如果不传 parent，回到上一个 node 的 edge 会被误判成 cycle。

Mistake 3: Directed Graph 使用 Parent Tracking

Parent tracking alone 不能正确检测所有 directed cycles。

Mistake 4: 没处理 Disconnected Graphs

只从 node 0 开始 DFS，可能漏掉其他 component 中的 cycle。

Mistake 5: 忘记 Mark Node as Fully Visited

Directed DFS 中，处理完 neighbors 后要：

state[node] = 2

Mistake 6: Course Schedule Edge Direction 写反

对于 prerequisite [course, prereq]，通常 edge 是：

prereq -> course

👉 面试回答

Cycle detection 常见错误包括：混用 directed 和 undirected logic、 undirected DFS 忘记 parent check、对 directed graph 使用 parent tracking、没处理 disconnected components、忘记把 node 标记为 fully visited，以及 Course Schedule 中 prerequisite edge direction 写反。

2️⃣3️⃣ 什么时候 Graph Cycle Detection 适用？

Good Fit

当题目问：

detect circular dependency
can finish all tasks
valid dependency order
redundant connection
whether graph is a tree
deadlock possibility
package dependency conflict
build order validation

Problem Signals

看到这些关键词想到 cycle detection：

cycle
circular
dependency
prerequisite
can finish
valid order
tree
redundant connection
deadlock
loop

👉 面试回答

当问题涉及 dependency validation、 circular relationships、判断 tasks 是否能完成、判断 graph 是否是 tree，或找到 redundant connection 时，我会考虑 cycle detection。

第一件事是判断 graph 是 directed 还是 undirected。

2️⃣4️⃣ 什么时候 Graph Cycle Detection 不适用？

Not Good Fit

Cycle detection 不足以解决：

need shortest path
need minimum spanning tree
need all possible paths
need connected components only
need strongly connected components
need max flow

Better Alternatives

Problem Type	Better Pattern
Shortest path	BFS / Dijkstra
Minimum total connection cost	MST / Kruskal / Prim
All valid paths	Backtracking / DFS
Connected components	DFS / BFS / Union Find
Strongly connected components	Tarjan / Kosaraju
Dependency ordering	Topological Sort
Dynamic connectivity	Union Find

👉 面试回答

Cycle detection 只回答是否存在 cycle。

如果题目问 shortest path、minimum spanning tree、 all paths 或 strongly connected components，就需要不同的 graph algorithm。

关键是判断 cycle 本身是不是主要约束。

2️⃣5️⃣ 标准模板

Undirected DFS Cycle Template

def has_cycle_undirected(n, graph):
    visited = set()

    def dfs(node, parent):
        visited.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True

        return False

    for node in range(n):
        if node not in visited:
            if dfs(node, -1):
                return True

    return False

Directed DFS State Template

def has_cycle_directed(n, graph):
    state = [0] * n

    def dfs(node):
        if state[node] == 1:
            return True

        if state[node] == 2:
            return False

        state[node] = 1

        for neighbor in graph[node]:
            if dfs(neighbor):
                return True

        state[node] = 2
        return False

    for node in range(n):
        if state[node] == 0:
            if dfs(node):
                return True

    return False

Topological Sort Cycle Template

from collections import deque

def has_cycle_topological(n, graph, indegree):
    queue = deque()

    for node in range(n):
        if indegree[node] == 0:
            queue.append(node)

    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1

        for neighbor in graph[node]:
            indegree[neighbor] -= 1

            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return processed != n

Union Find Cycle Template

def has_cycle_union_find(n, edges):
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])

        return parent[x]

    def union(a, b):
        root_a = find(a)
        root_b = find(b)

        if root_a == root_b:
            return False

        parent[root_b] = root_a
        return True

    for u, v in edges:
        if not union(u, v):
            return True

    return False

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Graph cycle detection 用来判断 graph 中是否存在一条 path，可以最终回到之前访问过的 node。

最重要的第一步是判断 graph 是 undirected 还是 directed，因为两者的 cycle detection 逻辑不同。

在 undirected graph 中，如果 DFS 访问到一个已经 visited 的 neighbor，并且这个 neighbor 不是 parent，就说明存在 cycle。 Parent check 很重要，因为 undirected edge 是双向的。看到 parent 是正常情况，看到其他 visited node 才说明存在 cycle。

对 undirected graph， Union Find 也是一个很好的方法。处理一条 edge 时，如果两个 endpoints 已经属于同一个 connected component，那么加入这条 edge 就会形成 cycle。否则，合并这两个 components。

在 directed graph 中， parent tracking 不够。我们需要知道 node 是否在当前 recursion path 中。常见 DFS 方法使用三个状态： unvisited、visiting 和 visited。如果 DFS 访问到 visiting node，就说明找到了 back edge，因此存在 directed cycle。

Topological sort 也可以检测 directed graph 中的 cycle。如果 graph 没有 cycle，我们应该可以不断处理 indegree 为 0 的 nodes。如果最后有 nodes 没有被处理，说明它们在 cycle 中，或者被 cycle 阻塞。

Course Schedule 是典型 directed cycle detection。每个 prerequisite 创建一条 dependency edge。如果有 cycle， courses 之间存在 circular dependency，因此无法完成所有课程。

Grid cycle detection 通常可以建模成 undirected graph cycle detection。每个 cell 是 node，相邻且字符相同的 cells 之间有 edge。

DFS 和 topological sort 的时间复杂度都是 O(V + E)。 Union Find 接近线性，是 O(E α(V))。

高级工程师解释 cycle detection 时，我会讲清楚： graph 是 directed 还是 undirected， cycle 在这个问题中代表什么，为什么 undirected graph 需要 parent tracking，为什么 directed graph 需要 recursion state，什么时候 topological sort 更有用，什么时候 Union Find 更简单，以及 disconnected graph 和 self-loop 这些 edge cases 如何处理。

⭐ Final Insight

Graph Cycle Detection 的核心不是“看到 visited 就 return true”。

它的核心是先判断 graph type：

undirected graph 需要 parent tracking， directed graph 需要 recursion state， dependency graph 可以用 topological sort， edge-by-edge undirected graph 可以用 Union Find。

Senior-level 的重点是：

cycle 在当前问题中代表什么， graph 是 directed 还是 undirected， visited 的含义是什么， parent 为什么只适用于 undirected graph， visiting state 为什么能检测 directed back edge， topological sort 为什么能发现 circular dependency，以及 disconnected graph 为什么必须全部遍历。

能讲清楚这些， Graph Cycle Detection 就是一类处理 circular dependency、redundant connection、valid ordering 和 graph validity 的核心模式。

🎯 Graph Cycle Detection

1️⃣ Core Framework

2️⃣ What Problem Are We Solving?

3️⃣ Cycle in Undirected Graph

Definition

Key Rule

Why Parent Matters

4️⃣ Undirected Graph DFS Template

Code

Why Loop All Nodes?

5️⃣ Cycle in Directed Graph

Definition

Key Difference

Three States

6️⃣ Directed Graph DFS Template

Code

State Meaning

7️⃣ Course Schedule

Problem

Graph Model

Code: DFS State

8️⃣ Course Schedule II

Problem

Topological Sort

Code: Kahn’s Algorithm

9️⃣ Topological Sort Cycle Detection

Kahn’s Algorithm

Code

🔟 DFS State vs Topological Sort

DFS State

Topological Sort

Comparison

1️⃣1️⃣ Union Find for Undirected Cycle

When to Use Union Find

Key Idea

Code

1️⃣2️⃣ Redundant Connection

Problem

Union Find Approach

Code

1️⃣3️⃣ Directed Cycle With Recursion Stack

Alternative Template

Code

1️⃣4️⃣ Cycle Detection in Grid

Problem

Model

Code

1️⃣5️⃣ Detect Cycle in Linked List

Related Pattern

Code

1️⃣6️⃣ Cycle Detection in Functional Graph

Functional Graph

Floyd’s Cycle Detection

Code

1️⃣7️⃣ Find Duplicate Number

Problem

Functional Graph Model

Code

1️⃣8️⃣ Cycle Detection in Dependency Graphs

Real-World Examples

Why Cycle Is Bad

Best Pattern

1️⃣9️⃣ Undirected vs Directed Cycle Detection

Undirected Graph

Directed Graph

Comparison

2️⃣0️⃣ Complexity Analysis

DFS Cycle Detection

Topological Sort

Union Find

2️⃣1️⃣ Common Edge Cases

Disconnected Graph

Self Loop

Parallel Edges

One Node

Directed Acyclic Graph

1-Indexed Nodes

2️⃣2️⃣ Common Mistakes

Mistake 1: Using Directed Logic for Undirected Graph

Mistake 2: Forgetting Parent in Undirected DFS