BFS and DFS compute components when you already have the whole graph. Union-find (DSU) maintains components while you union edges one at a time and find representatives in between.
Each node points at a parent. A root points at itself. find(x) walks to the root — that root is the component id. union(a, b) finds both roots and hangs one under the other. Two nodes are connected iff find(a) === find(b).
function createDsu(n) {
const parent = Array.from({ length: n }, (_, i) => i);
const rank = Array(n).fill(0);
function find(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]]; // compress one hop
x = parent[x];
}
return x;
}
function union(a, b) {
a = find(a);
b = find(b);
if (a === b) return false; // already same component
if (rank[a] < rank[b]) [a, b] = [b, a];
parent[b] = a;
if (rank[a] === rank[b]) rank[a]++;
return true;
}
return { find, union };
}Queries. 'Are u and v connected after the first k roads?' Sort the roads, union in order, find. 'Add this edge unless it makes a cycle' — union returning false means a cycle in an undirected graph (Kruskal's reject step). Counting components: start at n, subtract one on every successful merge.
DSU does not give distances or shortest paths. It only knows sameness of component. For unweighted distance, go back to BFS.
Checks 0/2