Cycle Detection

1. 1.Detect Cycle in an Undirected Graph
   Undirected DFS: check visited[neighbor] && neighbor != parentmedium
2. 2.Detect Cycle in a Directed Graph
   3-State Array (0=unvisited, 1=visiting, 2=finished); edge to state 1 implies back-edge cyclemedium
3. 3.Course Schedule
   Directed Cycle Detection / Kahn's Algorithm: deadlock cycle implies impossible course orderingmedium
4. 4.Course Schedule II
   Topological Sort via 3-State DFS or Kahn's Queue; detect cycle or return topological ordermedium
5. 5.Graph Valid Tree
   Undirected Graph: components == 1 AND no cycles (or edges == n - 1)medium
6. 6.Redundant Connection
   Union Find: find first edge where find(u) == find(v)medium
7. 7.Find Eventual Safe States
   3-State Directed Cycle DFS: terminal nodes and nodes not leading to cycles are safemedium
8. 8.Is Graph Bipartite?
   DFS 2-Coloring: odd-length cycle causes color conflictmedium
9. 9.Detect Cycle Using Union Find
   Iterate edge list; if Find(u) == Find(v) before union, cycle existsmedium
10. 10.Find the Duplicate Number
    Functional Graph: array values act as pointers i -> nums[i]; Floyd's Fast & Slow pointersmedium
11. 11.Circular Array Loop
    Functional Graph DFS / Fast & Slow pointers checking same-direction jumpsmedium
12. 12.Linked List Cycle
    Floyd's Fast & Slow Pointers (slow=1 step, fast=2 steps)easy
13. 13.Linked List Cycle II
    Fast & Slow collision -> reset slow to head & move both 1 step to find cycle entrymedium
14. 14.Alien Dictionary
    Character Dependency Directed Graph + 3-State Cycle Detection + Topological Sorthard
15. 15.Minimum Height Trees / Tree Validation Variants
    Kahn's leaf trimming / tree cycle validationmedium

1. 16.Find All Possible Recipes from Given Supplies
   Recipe Dependency Graph + Kahn's Topological Sort / Cycle Detectionmedium
2. 17.Parallel Courses
   Kahn's BFS level-by-level semester counting with cycle detectionmedium
3. 18.Remove Invalid Dependencies
   Directed Graph Cycle Removal / Feedback Arc Set variantshard
4. 19.Detect Cycle in Dependency Graph
   3-State Directed DFS on package/microservice dependency graphsmedium
5. 20.Strongly Connected Components
   Tarjan's or Kosaraju's algorithm for directed graph strongly connected component cycleshard
6. 21.Functional Graph Cycle Problems
   Graphs where out-degree of every node is 1; cycle entry & length calculationmedium
7. 22.Longest Cycle in a Graph
   Functional Graph DFS tracking node distance from current search roothard

How to Think

1. Undirected graph?DFS/BFS + Parent check (visited && neighbor != parent)
2. Directed graph?DFS + 3-State Array (0=unvisited, 1=visiting, 2=finished)
3. Edges arriving one by one?Union Find (Find(u) == Find(v) before union)
4. Every node points to 1 next node?Fast & Slow Pointers (Floyd's algorithm)

// 1. Undirected Graph DFS Cycle Detection: O(V + E) Time
func hasCycleUndirected(n int, adj [][]int) bool {
    visited := make([]bool, n)
    var dfs func(u, parent int) bool
    dfs = func(u, parent int) bool {
        visited[u] = true
        for _, v := range adj[u] {
            if !visited[v] {
                if dfs(v, u) { return true }
            } else if v != parent {
                return true // Visited neighbor AND not parent -> Cycle!
            }
        }
        return false
    }

    for i := 0; i < n; i++ {
        if !visited[i] && dfs(i, -1) { return true }
    }
    return false
}

// 2. Directed Graph 3-State DFS Cycle Detection: O(V + E) Time
// States: 0 = Unvisited, 1 = Visiting (active stack), 2 = Finished
func hasCycleDirected(n int, adj [][]int) bool {
    state := make([]int, n)
    var dfs func(u int) bool
    dfs = func(u int) bool {
        if state[u] == 1 { return true }  // Back Edge Cycle!
        if state[u] == 2 { return false } // Fully processed -> Safe!

        state[u] = 1 // Mark visiting
        for _, v := range adj[u] {
            if dfs(v) { return true }
        }
        state[u] = 2 // Mark finished
        return false
    }

    for i := 0; i < n; i++ {
        if state[i] == 0 && dfs(i) { return true }
    }
    return false
}

// 3. Union Find Cycle Detection (Redundant Connection): O(E · α(V)) Time
func findRedundantConnection(edges [][]int) []int {
    n := len(edges)
    parent := make([]int, n+1)
    for i := 1; i <= n; i++ { parent[i] = i }

    var find func(i int) int
    find = func(i int) int {
        if parent[i] != i { parent[i] = find(parent[i]) }
        return parent[i]
    }

    for _, edge := range edges {
        u, v := edge[0], edge[1]
        rootU, rootV := find(u), find(v)
        if rootU == rootV {
            return edge // Endpoints already connected -> Redundant Cycle Edge!
        }
        parent[rootV] = rootU
    }
    return nil
}

Undirected Parent Rule vs Directed 3-State Array

Union Find & Fast & Slow Pointer Cycles

Undirected Cycle → Visited neighbor && neighbor != parent
Directed Cycle   → Edge to state 1 (Visiting / Active Stack)
3-State Array    → 0=unvisited, 1=visiting, 2=finished
Union Find Cycle → Find(u) == Find(v) before union
Fast & Slow      → Functional graph (out-degree 1) cycle collision

Common Interview Mistakes

Interview Rules

1. 1. Undirected graph cycle? → Visited + Parent check (visited[neighbor] && neighbor != parent)
2. 2. Directed graph cycle? → 3-State Array (0=unvisited, 1=visiting, 2=finished). Edge to state 1 = cycle
3. 3. Course Schedule / Dependency Deadlock?→ Directed Cycle Detection or Kahn's Topological Sort
4. 4. Incremental undirected edges? → Union Find (Find(u) == Find(v) before union)
5. 5. Functional graph (out-degree 1)?→ Floyd's Fast & Slow pointers (slow=1, fast=2)
6. 6. Graph Valid Tree? → Components == 1 AND no cycles (or edges == n - 1)
7. 7. Disconnected Graph? → Outer loop over all 0..n-1 nodes
8. 8. Overall Complexity → Traversal Time: O(V + E) | Union Find Time: O(E · α(V))

Cycle Detection

Undirected       → Visited + Parent check
Visited != parent → Cycle

Directed         → 0 / 1 / 2 states
Edge to Visiting → Cycle

Kahn's BFS       → Nodes left unprocessed = Cycle
Union Find       → Same root before union = Cycle
Fast & Slow      → Functional graph (out-degree 1)
Time             → O(V + E)

💡 Golden Rule: "In an undirected graph, ignore the edge you came from; in a directed graph, a cycle exists when you reach a node that is still inside the current DFS path."