Union Find / Disjoint Set Union

1. 1.Number of Connected Components in an Undirected Graph
   Initialize DSU with n components; decrement on every successful Union(u, v)medium
2. 2.Redundant Connection
   Iterate edges; return the edge where Union(u, v) returns false (already connected)medium
3. 3.Number of Provinces
   Union cities i and j if isConnected[i][j] == 1; return remaining DSU component countmedium
4. 4.Graph Valid Tree
   Verify edges == n - 1 and all Union(u, v) succeed without cyclesmedium
5. 5.Accounts Merge
   Map each email to an account index; Union accounts sharing emails; group emails by rootmedium
6. 6.Most Stones Removed with Same Row or Column
   Union stones sharing row or column; max removals = total stones - component countmedium
7. 7.Number of Operations to Make Network Connected
   Check if total edges >= n - 1; answer = remaining components - 1medium
8. 8.Satisfiability of Equality Equations
   Union variables in "a==b"; verify for all "c!=d" that Find(c) != Find(d)medium
9. 9.Smallest String With Swaps
   Union indices in swap pairs; sort characters within each component rootmedium
10. 10.Similar String Groups
    Union pairs of words that differ by <= 2 swap positions; return component counthard
11. 11.Regions Cut By Slashes
    Divide each grid square into 4 triangles; Union adjacent triangles separated by slashesmedium
12. 12.Largest Component Size by Common Factor
    Union each number with its prime factors; return largest DSU component sizehard
13. 13.Min Cost to Connect All Points
    Build Manhattan distance edges + Kruskal's MST using Union Findmedium
14. 14.Kruskal's Minimum Spanning Tree
    Sort edges by weight; add edge if Union(u, v) succeeds (endpoints in different components)medium
15. 15.Number of Islands II
    Add land dynamically; Union neighboring 4-direction land cells; update island counthard
16. 16.Remove Max Number of Edges to Keep Graph Fully Traversable
    Dual DSU for Alice & Bob; prioritize Type 3 shared edges firsthard
17. 17.Checking Existence of Edge Length Limited Paths
    Offline queries sorted by limit + Kruskal DSU edge additionshard
18. 18.Find Critical and Pseudo-Critical Edges in MST
    Kruskal DSU MST forcing vs excluding individual edgeshard

1. 19.Sentence Similarity II
   Union similar word pairs; query Find(w1) == Find(w2)medium
2. 20.Connecting Cities With Minimum Cost
   Standard Kruskal's MST using Union Findmedium
3. 21.Earliest Moment When Everyone Becomes Friends
   Sort timestamped friend logs; return time when DSU component count reaches 1medium
4. 22.Minimize Malware Spread
   Find component sizes of infected nodes; pick node whose removal maximizes clean component counthard
5. 23.Couples Holding Hands
   Union pairs of seats (2i, 2i+1); min swaps = N - DSU component counthard
6. 24.Friend Requests with Restrictions
   Simulate friend requests using DSU; check restriction rules before Unionhard
7. 25.Dynamic Connectivity Problems
   Advanced DSU with Rollback & segment tree query decompositionhard

How to Think

1. Need repeatedly ask: are these connected?Union Find (DSU)
2. Need merge groups?Union(u, v)
3. Need representative of a group?Find(u)
4. Adding edge creates cycle?Find(u) == Find(v) before edge addition
5. Need Minimum Spanning Tree?Kruskal's Algorithm + DSU

type DSU struct {
    parent []int
    size   []int
}

func NewDSU(n int) *DSU {
    p := make([]int, n)
    s := make([]int, n)
    for i := 0; i < n; i++ {
        p[i] = i
        s[i] = 1
    }
    return &DSU{parent: p, size: s}
}

// Find with Path Compression: O(alpha(N)) amortized (~O(1))
func (d *DSU) Find(x int) int {
    if d.parent[x] != x {
        d.parent[x] = d.Find(d.parent[x]) // Flatten tree!
    }
    return d.parent[x]
}

// Union by Size: O(alpha(N)) amortized (~O(1))
func (d *DSU) Union(a, b int) bool {
    rootA := d.Find(a)
    rootB := d.Find(b)

    if rootA == rootB {
        return false // Already connected! Same root -> Cycle detected!
    }

    // Attach smaller tree under larger tree
    if d.size[rootA] < d.size[rootB] {
        rootA, rootB = rootB, rootA
    }
    d.parent[rootB] = rootA
    d.size[rootA] += d.size[rootB]
    return true // Successful merge!
}

Path Compression & Union by Size

Undirected Cycle Detection & Kruskal MST

DSU / Union Find → Efficiently track and merge connected components
Find(x)          → parent[x] = Find(parent[x]) (Path Compression -> O(1))
Union(a, b)      → Merge smaller root under larger root (Union by Size)
Find(u) == Find(v) -> Nodes already connected! Undirected Cycle Detected!
Kruskal MST      → Sort edges by weight -> Add edge if Union(u, v) succeeds
Accounts Merge   → Shared email identifier -> Union account IDs

Common Interview Mistakes

Interview Rules

1. 1. Repeated connectivity queries? → Union Find / DSU
2. 2. Find representative root? → parent[x] = Find(parent[x]) (Path Compression)
3. 3. Merge groups? → Attach smaller root under larger root (Union by Size)
4. 4. Same root check? → Find(u) == Find(v)
5. 5. Undirected cycle check? → If Find(u) == Find(v) before adding edge $\implies$ Cycle!
6. 6. Redundant Connection? → Return edge where Union(u, v) == false
7. 7. Minimum Spanning Tree? → Sort edges by weight + Kruskal DSU
8. 8. Overall Complexity → Time: O(α(N)) ≈ O(1) per operation | Space: O(N)

Union Find / DSU → Track & Merge Disjoint Groups

Find(x)          → parent[x] = Find(parent[x]) (Path Compression)
Union(a, b)      → Merge smaller root under larger root (Union by Size)
Same Root        → Find(a) == Find(b) (Connected!)
Cycle Check      → Find(u) == Find(v) before adding edge
Components       → Start N, successful Union: --
Kruskal MST      → Sort edges by weight + Union Find
Time             → O(alpha(N)) per operation ≈ O(1)

💡 Golden Rule: "Every connected group has one representative root; Find tells you the group, and Union merges two different groups into one."