Union-Find & Minimum Spanning Trees

Nowhere else — that's the trick. A group is just "everyone whose find gives the same root"; the DSU keeps no member list. When a problem wants the groups themselves (Accounts Merge), loop over every element once and bucket it by its root: map.computeIfAbsent(find(i), k -> new ArrayList<>()).add(i).

Take the chain 3 → 2 → 1 → 0, where 0 is the root. find(3) calls find(2), which calls find(1), which calls find(0) and gets 0 back. On the way back each call stores that answer: parent[1] = 0, then parent[2] = 0, then parent[3] = 0. Simple hai — the calls go up to find the root, and the return trip re-points every node, so the next find(3) is one hop.

Yes, a single find can walk a longer path once. But it then flattens that path, so later finds are cheap. Averaged over any sequence of m operations, the cost is O(m·α(n)) total. α grows so slowly that it is at most 4 for any realistic n, so you can call it "near-constant".

Each alone gives O(log n) (worst case for size/rank, amortized for compression). Together they give O(α(n)). In interviews, write both — it is only two extra lines.

No. Compression only moves nodes within one tree, so the set and the root stay the same and the root's size stays correct. Rank becomes an upper bound on height instead of the exact height — which is all the analysis needs.

For a fixed graph you traverse once (count islands, find a path), DFS/BFS is just as fast and needs no extra structure. Union-Find wins when edges arrive one by one and you need connectivity answers in between, or when the input is a plain list of pairs.

Being connected is transitive. If every email is joined to the first one, they all land in one set — k emails need only k − 1 unions (a star shape). Joining every pair would cost about k²/2 unions for the same result. And an email that appears in two accounts automatically bridges both sets.

A != check is only valid once the groups are final. Example: a!=c, a==b, b==c. Checked in that order, a!=c looks fine because a and c are still apart — then the two == merge them. Two passes fix it: first union all the ==, then test each != against the finished groups.

A component with k computers needs only k − 1 cables; every extra cable inside it is spare. With c components the needed cables add up to n − c, so spares = cables − (n − c). If cables ≥ n − 1, spares ≥ (n − 1) − (n − c) = c − 1 — exactly the moves needed to join c pieces.

Cut property: split the nodes into two sides, and the cheapest edge crossing the split belongs to some MST (if a tree skipped it, swapping it in for the tree's crossing edge would make the tree no heavier). Now split one endpoint's group from everything else. Every cheaper edge was already taken or joined two nodes in the same group, so Kruskal's next accepted edge is the cheapest one crossing that split.

Kruskal if you are given an edge list (sort + DSU is short and hard to get wrong). Prim if you have an adjacency list, or the O(V²) array version when every pair of nodes is connected (like LC 1584).

Any start node works: the tree it grows always has the minimum total weight (with tied weights the chosen edges may differ, the total never does). But Prim only grows inside the start node's component. If it reaches fewer than n nodes, the graph is disconnected and there is no spanning tree — Kruskal shows the same thing by ending with fewer than n − 1 edges.

No. An MST minimises the total weight of the tree; the path between two nodes inside the MST can be much longer than the shortest path (Dijkstra). Different goals, different algorithms.

No. Kruskal and Prim only compare weights, so negatives are fine. Equal weights just mean the MST may not be unique — but every MST has the same total weight. (With all weights distinct, the MST is unique.)