Hints — p65 Number of Connected Components

Hint 1. Two approaches: DFS/BFS over adjacency list, OR Union-Find (DSU). Both O(V+E)-ish, but DSU is the canonical answer here and tests an important data structure.

Hint 2. DSU basics: parent[i] = i initially. find(x) walks parents to root. union(x, y) joins two roots. Component count = number of distinct roots = n − (successful unions).

Hint 3. Optimization 1 — path compression (or halving): inside find, redirect parents toward the root. Iterative halving avoids recursion-limit risk: parent[x] = parent[parent[x]]; x = parent[x].

Hint 4. Optimization 2 — union by rank: track approximate tree depth (rank). When unioning, hang the shorter tree under the taller. Rank increases only on ties.

Hint 5. Together: O(α(n)) per operation amortized (inverse Ackermann, ~constant ≤ 4 for all practical n). Decrement a components counter on every SUCCESSFUL union (when roots differ). Final count = n − merges.

If stuck: see solution.py.