DSU Practice Test: Union-Find, Kruskal's MST in C++
A timed union-find checkpoint: ten questions on path compression, union by size and cycles, then Kruskal's MST and online connectivity in C++.
- Course: Competitive Programming study plan
- Module: Disjoint set union (DSU)
- Kind: Checkpoint — cleared at 70%
- Reading time: 45 min
- Runtime: Clang 18 · C++20
Checkpoint — Disjoint set union is the checkpoint that closes the Disjoint set union (DSU) module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
A 45-minute timed checkpoint on module 7: the DSU, its two speed rules, and the problems it solves.
How it works. Ten questions and two programs, in 45 minutes from when you start the timer. 70% on the questions and both programs accepted clears the module.
Before you start, make sure you can answer these from memory:
- What
findreturns, and what path compression changes on the way back. - Why union by size keeps every tree at most log2 n tall.
- What
unitereturningfalsemeans for an edge of a graph. - How Kruskal's algorithm decides whether to take an edge, and how it knows the graph was disconnected.
The programs are Kruskal's minimum spanning tree with weights up to 10^9, and a stream of union and "same set?" queries answered online.
Common questions
How does Kruskal's algorithm use a DSU?
Sort the edges by weight and take them cheapest first; an edge joins the tree only when unite succeeds, meaning its endpoints were in different components. After n − 1 successful unites the edges taken form a minimum spanning tree; fewer means the graph is disconnected.
Why is the answer to Kruskal's algorithm a long long?
A spanning tree has n − 1 edges, and with weights up to 10^9 just three of them already sum past 2^31. Accumulate the total in long long from the start.
Exercises
Kruskal's minimum spanning tree
A weighted undirected graph has vertices 1 to n and m edges. Print the total weight of a minimum spanning tree, or IMPOSSIBLE when the graph is not connected. (With n = 1 the tree has no edges and weighs 0.)
Input: n m, then m lines u v w (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2·10^5, 1 ≤ w ≤ 10^9; self-loops and parallel edges may appear). Output: one line.
4 5
1 2 3
2 3 1
3 4 4
1 4 2
1 3 5prints
6The tree takes 2-3 (1), 1-4 (2) and 1-2 (3).
Union and query, online
There are n elements 1 to n, each in its own set. Process q operations in order:
U a b— merge the sets ofaandb;Q a b— printYESifaandbare in the same set right now,NOotherwise.
Input: n q, then q lines (1 ≤ n, q ≤ 2·10^5). There is at least one Q. Output: one line per Q.
5 6
Q 1 2
U 1 2
U 3 4
Q 2 1
U 2 4
Q 1 3prints
NO
YES
YESIn this module: Disjoint set union (DSU)
← Disjoint set union — union by size and path compression · Shortest paths — BFS, 0-1 BFS and Dijkstra →