Connected Components

1. 1.Number of Provinces
   Adjacency Matrix: outer loop 0..n-1; if !visited[i] -> components++ & DFS(i)medium
2. 2.Number of Connected Components in an Undirected Graph
   Build Adjacency List; outer loop unvisited nodes to count DFS triggersmedium
3. 3.Number of Islands
   Grid Components: scan cells; if grid[r][c] == "1" -> islands++ & Grid DFS/BFSmedium
4. 4.Max Area of Island
   Grid DFS returning 1 + sum(dfs(neighbor)) per component; track max areamedium
5. 5.Graph Valid Tree
   Connected Components == 1 AND edges == n - 1medium
6. 6.Accounts Merge
   Email Graph / Union Find: Emails sharing an account form graph edgesmedium
7. 7.Friend Circles / Provinces
   Adjacency Matrix DFS component countmedium
8. 8.Count Sub Islands
   Grid DFS: island in grid2 is sub-island if all its cells are land in grid1medium
9. 9.Closed Islands
   Boundary Grid DFS: flood fill border land, count remaining closed islandsmedium
10. 10.Number of Enclaves
    Boundary Grid DFS: flood fill boundary land, count remaining unreached land cellsmedium
11. 11.Find if Path Exists in Graph
    Verify if source and destination belong to same connected componenteasy
12. 12.Redundant Connection
    Union Find: find first edge where find(u) == find(v)medium
13. 13.Smallest String With Swaps
    Union Find / Component DFS: group indices into components & sort characters inside each componentmedium
14. 14.Similar String Groups
    Connect similar strings with edges + Connected Components DFShard
15. 15.Most Stones Removed with Same Row or Column
    Connect stones in same row/col; max stones removed = totalStones - numComponentsmedium
16. 16.Number of Operations to Make Network Connected
    If edges < n - 1 return -1; operations needed = numComponents - 1medium

1. 17.Surrounded Regions
   Boundary Grid DFS: flood fill border "O"s, capture remaining "O"s to "X"medium
2. 18.Largest Component Size by Common Factor
   Union Find connecting numbers to their prime factorshard
3. 19.Regions Cut By Slashes
   Split each grid cell into 4 sub-triangles + Union Find connectivitymedium
4. 20.Number of Distinct Islands
   Grid DFS + path shape serialization (e.g. "U", "D", "L", "R", "B") stored in Hash Setmedium
5. 21.Count Unreachable Pairs of Nodes
   Compute component sizes; answer = sum(size * (n - size)) / 2medium
6. 22.Satisfiability of Equality Equations
   Union Find: union equal variables "a==b", verify non-equals "a!=b" have different rootsmedium
7. 23.Sentence Similarity II
   Map-based Graph / Union Find checking word pair connectivitymedium
8. 24.Accounts / User Identity Grouping
   Identity Deduplication Graph: merge user profiles sharing phone/emailmedium

How to Think

1. Need count separate groups?Connected Components (Outer loop DFS/BFS)
2. Need size of each group?DFS/BFS + increment size++ during traversal
3. Need merge groups dynamically as edges arrive?Union Find (Disjoint Set Union)
4. Grid contains separate land regions?Connected Components on Grid (Islands)

// 1. Connected Components DFS: O(V + E) Time
func countComponents(n int, edges [][]int) int {
    adj := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        adj[u] = append(adj[u], v)
        adj[v] = append(adj[v], u)
    }

    visited := make([]bool, n)
    var dfs func(u int)
    dfs = func(u int) {
        visited[u] = true
        for _, neighbor := range adj[u] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }

    components := 0
    // Outer loop over ALL n nodes (includes isolated nodes of size 1!)
    for i := 0; i < n; i++ {
        if !visited[i] {
            components++
            dfs(i)
        }
    }
    return components
}

// 2. Union Find (Disjoint Set Union): O(E · α(V)) Time
type UnionFind struct {
    parent []int
    rank   []int
    count  int
}

func NewUnionFind(n int) *UnionFind {
    p := make([]int, n)
    r := make([]int, n)
    for i := 0; i < n; i++ { p[i] = i }
    return &UnionFind{parent: p, rank: r, count: n}
}

func (uf *UnionFind) Find(i int) int {
    if uf.parent[i] != i {
        uf.parent[i] = uf.Find(uf.parent[i]) // Path Compression!
    }
    return uf.parent[i]
}

func (uf *UnionFind) Union(i, j int) bool {
    rootI, rootJ := uf.Find(i), uf.Find(j)
    if rootI == rootJ { return false } // Already in same component!
    
    // Union by Rank
    if uf.rank[rootI] < uf.rank[rootJ] {
        rootI, rootJ = rootJ, rootI
    }
    uf.parent[rootJ] = rootI
    if uf.rank[rootI] == uf.rank[rootJ] {
        uf.rank[rootI]++
    }
    uf.count--
    return true
}

The Golden Outer Loop Discovery Pattern

DFS/BFS vs Union Find Tradeoffs

Connected Components → Separate reachable groups in an undirected graph
Outer Loop Trigger   → for node 0..n-1: if !visited[i] -> components++ & DFS(i)
Component Size       → Count size++ during traversal (Max Area, Unreachable Pairs)
Static Graph         → DFS / BFS (O(V + E) Time)
Dynamic Merges       → Union Find (O(E · α(V)) Time)

Common Interview Mistakes

Interview Rules

1. 1. Count separate groups? → Connected Components (Outer loop DFS/BFS)
2. 2. Group size required? → Increment size++ during DFS/BFS traversal
3. 3. Grid Islands / Provinces? → 2D Cell Grid Connected Components
4. 4. Dynamic edge merging? → Union Find (Disjoint Set Union)
5. 5. Isolated nodes? → Count as component of size 1 (outer loop covers all n nodes)
6. 6. Graph Valid Tree? → Components == 1 AND edges == n - 1
7. 7. Most Stones Removed? → Answer = totalStones - numComponents
8. 8. Overall Complexity → Traversal Time: O(V + E) | Union Find Time: O(E · α(V))

Connected Components → Separate reachable groups
Loop all nodes
Unvisited?           → components++
Then                 → DFS/BFS marks whole group
Grid islands         → Matrix components
Component size       → Count nodes during traversal
Dynamic merging      → Union Find
Isolated node        → Component of size 1
Time                 → O(V + E)

💡 Golden Rule: "Every time you find a node that no previous traversal could reach, you have found a new connected component."