Track connectivity with union-find
Join pairs of elements into groups and answer whether two elements belong to the same connected component.
Course progress
Problem 81 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
union(0,1), union(1,2), union(3,4); queries (0,2) and (0,4)
Expected output
True False
What is happening?
0, 1, and 2 share one representative, so 0 and 2 are connected. The separate 3,4 group has never been joined to them, so 0 and 4 are not.
Solution strategy
Build the right mental model
Represent each group as a parent tree, compress paths during lookup, and attach the shorter tree below the taller one during union.
Core concepts
disjoint set · path compression
Complexity
Amortized time O(alpha(n)) per operation, space O(n).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for union-find-connectivity
using System;
class Program
{
class DisjointSet
{
private readonly int[] parent;
private readonly int[] rank;
public DisjointSet(int size)
{
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) parent[i] = i;
}
public int Find(int value)
{
if (parent[value] != value) parent[value] = Find(parent[value]);
return parent[value];
}
public void Union(int first, int second)
{
int rootFirst = Find(first), rootSecond = Find(second);
if (rootFirst == rootSecond) return;
if (rank[rootFirst] < rank[rootSecond]) parent[rootFirst] = rootSecond;
else if (rank[rootFirst] > rank[rootSecond]) parent[rootSecond] = rootFirst;
else { parent[rootSecond] = rootFirst; rank[rootFirst]++; }
}
public bool Connected(int first, int second) { return Find(first) == Find(second); }
}
static void Main()
{
var sets = new DisjointSet(6);
sets.Union(0, 1);
sets.Union(1, 2);
sets.Union(3, 4);
Console.WriteLine(sets.Connected(0, 2));
Console.WriteLine(sets.Connected(0, 4));
}
}Knowledge check
Questions students often ask
What is the main idea behind track connectivity with union-find?
Represent each group as a parent tree, compress paths during lookup, and attach the shorter tree below the taller one during union.
What is the time and space complexity of this solution?
Amortized time O(alpha(n)) per operation, space O(n).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.