The challenge
Maintain components while undirected connections are added. Support find(u), union(u, v), and checking whether two vertices are connected.
Supports adding connections. Basic DSU does not support deletions or directed reachability.
Example
Union A–B, then B–C. Now find(A) equals find(C); union(A, C) returns false because they are already connected.
Use the walkthrough below to inspect the input and each state change.
See Union-Find, step by step
Follow the edges. Watch the state change.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| A | B | C | D | E | F |
Start with one component per vertex.
Process the undirected edges as union operations. Representatives identify connectivity, not literal graph edges.
parent[u] = u; size[u] = 1Connectivity
View input edges
A — B (4) · A — F (1) · F — B (2) · B — C (1) · F — E (8) · C — D (3) · D — E (1)
Put it into code
Represent each component as a parent tree and make repeated finds cheaper.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.components = n
def find(self, u):
while u != self.parent[u]:
self.parent[u] = self.parent[self.parent[u]]
u = self.parent[u]
return u
def union(self, u, v):
a, b = self.find(u), self.find(v)
if a == b:
return False
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
self.components -= 1
return True
# Example: vertices 0..5 (A..F in the diagram).
dsu = DSU(6)
dsu.union(0, 1)
dsu.union(1, 2)
connected = dsu.find(0) == dsu.find(2) # True
merged = dsu.union(0, 2) # False: already in one component.#include <numeric>
#include <utility>
#include <vector>
struct DSU {
std::vector<int> parent, size;
int components;
explicit DSU(int n) : parent(n), size(n, 1), components(n) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int u) {
while (u != parent[u]) {
parent[u] = parent[parent[u]];
u = parent[u];
}
return u;
}
bool unite(int u, int v) {
int a = find(u), b = find(v);
if (a == b) return false;
if (size[a] < size[b]) std::swap(a, b);
parent[b] = a;
size[a] += size[b];
--components;
return true;
}
};
// Example: vertices 0..5 (A..F in the diagram).
bool connectivity_example() {
DSU dsu(6);
dsu.unite(0, 1);
dsu.unite(1, 2);
return dsu.find(0) == dsu.find(2); // true
}