Graph DFS

1. 1.Number of Islands
   Grid DFS: loop unvisited "1"s; trigger DFS to flood fill entire land mass to "0"medium
2. 2.Clone Graph
   DFS + HashMap mapping original node -> cloned node; save clone in map BEFORE neighbor recursionmedium
3. 3.Number of Provinces
   Adjacency Matrix DFS: count unvisited node triggers to discover total connected componentsmedium
4. 4.Max Area of Island
   Grid DFS returning 1 + sum(dfs(neighbor)) for each connected land cellmedium
5. 5.Flood Fill
   4-directional Grid DFS: change matching starting color cells to new color (check startColor != newColor)easy
6. 6.Surrounded Regions
   Boundary DFS: start DFS from border "O"s to mark safe cells; capture remaining internal "O"s to "X"medium
7. 7.Pacific Atlantic Water Flow
   Reverse DFS from Pacific and Atlantic borders inward; answer is cell intersection setmedium
8. 8.Course Schedule
   3-State Directed Cycle DFS (0=unvisited, 1=visiting, 2=finished); encountering state 1 implies cycle deadlockmedium
9. 9.Graph Valid Tree
   Undirected Cycle DFS: check edges == n - 1 AND 1 DFS from node 0 visits all n nodesmedium
10. 10.Is Graph Bipartite?
    DFS 2-coloring: assign neighbor color = 1 - currColor; if neighbor has same color -> return falsemedium
11. 11.Keys and Rooms
    DFS reachability starting from room 0 using visited boolean arraymedium
12. 12.All Paths From Source to Target
    DAG DFS + Backtracking: append node to path, recurse, then pop node after returnmedium
13. 13.Reorder Routes to Make All Paths Lead to Zero
    Undirected DFS from 0 tracking original direction vs artificial reverse edge costsmedium
14. 14.Evaluate Division
    Weighted Directed Graph DFS: find product of edge weights along query path u -> vmedium
15. 15.Detonate the Maximum Bombs
    Directed DFS from each bomb u: edge u -> v exists if dist(u,v) <= radius(u)medium
16. 16.Find Eventual Safe States
    3-State Directed Cycle DFS: terminal nodes and nodes leading only to safe nodes are safemedium
17. 17.Possible Bipartition
    Build dislike graph + DFS 2-coloringmedium
18. 18.Accounts Merge
    Email Graph DFS / Union Find: merge emails belonging to same accountmedium
19. 19.Redundant Connection
    DFS Cycle Detection / Disjoint Set Union on undirected edge listmedium
20. 20.Number of Connected Components
    Loop all n nodes; if unvisited, increment count & run DFSmedium

1. 21.Path With Maximum Gold
   Grid DFS + Backtracking (mark cell 0 -> explore 4 directions -> restore original gold value)medium
2. 22.Word Search
   Grid DFS + Backtracking: match character, mark visited, recurse 4 directions, unmark cellmedium
3. 23.Count Sub Islands
   Grid DFS: island in grid2 is sub-island only if all its cells are land in grid1medium
4. 24.Closed Islands
   Boundary Grid DFS: eliminate land connected to grid borders, count remaining closed islandsmedium
5. 25.Number of Enclaves
   Boundary Grid DFS: flood fill land connected to boundary, return count of remaining land cellsmedium
6. 26.Coloring a Border
   Grid DFS: color cell if it is on grid boundary or has an adjacent cell with different initial colormedium
7. 27.Find if Path Exists in Graph
   Basic Graph DFS / BFS reachability from source to destinationeasy
8. 28.Minimum Height Trees
   Tree DFS / Kahn's leaf trimming to locate tree centersmedium
9. 29.Longest Increasing Path in a Matrix
   Grid DFS + Memoization memo[r][c] storing longest strictly increasing path starting at cell (r,c)hard
10. 30.Critical Connections in a Network
    Tarjan's Bridge-Finding DFS algorithm using discovery time and lowest reachability arrayshard

How to Think

1. Need explore one connected region?DFS (Go deep along paths)
2. Need count connected groups?DFS + Visited Set
3. Need detect cycles?DFS + 3-State Array (0=unvisited, 1=visiting, 2=finished)
4. Need explore every possible path?DFS + Backtracking (Unmark upon return)
5. Matrix has connected cells?Grid DFS (4-directional offsets)

// 1. Standard Graph DFS (Connected Components): O(V + E) Time
func graphDFS(n int, adj [][]int) int {
    visited := make([]bool, n)
    components := 0

    var dfs func(u int)
    dfs = func(u int) {
        visited[u] = true // Mark immediately upon entry!
        for _, neighbor := range adj[u] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            components++
            dfs(i)
        }
    }
    return components
}

// 2. Directed Cycle Detection (Course Schedule 3-State DFS)
// States: 0 = Unvisited, 1 = Visiting (active DFS path), 2 = Finished
func canFinish(numCourses int, prerequisites [][]int) bool {
    adj := make([][]int, numCourses)
    for _, p := range prerequisites {
        adj[p[1]] = append(adj[p[1]], p[0])
    }

    state := make([]int, numCourses)

    var hasCycle func(u int) bool
    hasCycle = func(u int) bool {
        if state[u] == 1 { return true }  // Found node in active DFS path -> Cycle!
        if state[u] == 2 { return false } // Fully processed node -> Safe!

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

    for i := 0; i < numCourses; i++ {
        if state[i] == 0 && hasCycle(i) {
            return false // Cycle found -> Cannot finish all courses!
        }
    }
    return true
}

// 3. Grid DFS (Number of Islands / Max Area): O(R · C) Time
func numIslands(grid [][]byte) int {
    rows, cols := len(grid), len(grid[0])
    islands := 0

    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1' {
            return
        }
        grid[r][c] = '0' // Sink island / mark visited!
        dfs(r-1, c); dfs(r+1, c); dfs(r, c-1); dfs(r, c+1)
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == '1' {
                islands++
                dfs(r, c)
            }
        }
    }
    return islands
}

Cycle Detection States: Undirected vs Directed

Permanent Visited vs Path Backtracking Unmarking

Graph DFS        → Go deep along paths using call stack LIFO structure
Visited Set      → MANDATORY! Mark immediately upon entry (visited[u] = true)
Component Count  → Outer loop over all nodes; new DFS trigger = 1 new component
Directed Cycle   → 3-State Array (0=unvisited, 1=visiting, 2=finished)
Backtracking     → Mark -> Recurse -> UNMARK (visited[u] = false)

Common Interview Mistakes

Interview Rules

1. 1. Explore connected region / group? → Graph DFS
2. 2. When to mark visited? → Mark visited[u] = true immediately upon entry
3. 3. Count connected components?→ Outer loop over all nodes; if unvisited, increment count & trigger DFS
4. 4. Directed Cycle Detection (Course Schedule)? → 3-State Array (0=unvisited, 1=visiting, 2=finished)
5. 5. Undirected Cycle Detection? → Check visited[neighbor] && neighbor != parent
6. 6. Explore all paths? → DFS + Backtracking (unmark node upon return)
7. 7. Repeated subproblem work on Matrix/Graph? → DFS + Memoization (memo[r][c])
8. 8. Overall Complexity → Time: O(V + E) | Stack Space: O(V)

Graph DFS        → Go Deep
Visited          → Prevent cycles & repeats
Basic Pattern    → Mark -> Explore neighbors
Components       → New DFS = New Group
Grid             → Cell = Node
All Paths        → DFS + Backtracking
Undirected Cycle → Parent check
Directed Cycle   → 3-State (0=unvisited, 1=visiting, 2=finished)
Clone Graph      → DFS + Map
Repeated States  → DFS + Memo
Time             → O(V + E)

💡 Golden Rule: "Mark where you have been, follow one path as deep as possible, and only return when that path has nothing new left to explore."