Union-Find preview

Union-Find (Disjoint Set Union) tracks connected components with find and union—nearly O(1) amortized with path compression and union by rank. Used in Kruskal MST, network connectivity.

Operations

• find(x) — representative of x's set
• union(a,b) — merge sets containing a and b
• connected(a,b) — find(a) == find(b)

Simple implementation

#include 
#include 

struct DSU {
    std::vector p;
    DSU(int n) : p(n) { for (int i = 0; i < n; ++i) p[i] = i; }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    void unite(int a, int b) { a = find(a); b = find(b); if (a != b) p[a] = b; }
};

int main() {
    DSU dsu(5);
    dsu.unite(0, 1); dsu.unite(2, 3);
    std::cout << (dsu.find(0) == dsu.find(1) ? "same\n" : "diff\n");
    return 0;
}

Kruskal preview

Sort edges by weight; add edge if endpoints in different sets—MST greedy with DSU.

Important interview questions and answers

1. Q: Path compression?
   A: During find, point nodes directly to root—flattens tree.
2. Q: Union by rank/size?
   A: Attach smaller tree under larger—keeps depth small.

Self-check

1. What do find and union do?
2. Why DSU helps Kruskal MST?

Tip: Path compression in find is one line that impresses in DSU interviews.