Learn Disjoint Set Union DSU — Free DSA Tutorial

What is DSU

Disjoint Set Union (Union-Find) keeps track of a collection of elements split into separate, non-overlapping groups, and answers two questions efficiently: which group does an element belong to, and are two elements in the same group.

Example: What is DSU

#include <iostream>
using namespace std;
int main() {
	cout << "DSU tracks separate groups, answers 'same group?' and merges two groups efficiently";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("DSU tracks separate groups, answers 'same group?' and merges two groups efficiently");
	}
}

print("DSU tracks separate groups, answers 'same group?' and merges two groups efficiently")

#include <stdio.h>
int main() {
	printf("DSU tracks separate groups, answers 'same group?' and merges two groups efficiently");
	return 0;
}

Find Operation

The find operation walks up from an element through parent pointers until it reaches that group's representative (its root), so two elements are in the same set exactly when find returns the same representative for both.

Example: Find Operation

#include <iostream>
using namespace std;
int parent[5] = {0,0,1,3,3};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
int main() { cout << "Root of element 2: " << find(2); return 0; }

public class Main {
	static int[] parent = {0,0,1,3,3};
	static int find(int x) { return parent[x]==x ? x : find(parent[x]); }
	public static void main(String[] args) { System.out.println("Root of element 2: " + find(2)); }
}

parent = [0,0,1,3,3]
def find(x):
    return x if parent[x] == x else find(parent[x])
print("Root of element 2:", find(2))

#include <stdio.h>
int parent[5] = {0,0,1,3,3};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
int main() { printf("Root of element 2: %d", find(2)); return 0; }

Union Operation

The union operation merges two different sets into one by pointing one set's representative to point at the other's, effectively joining two previously separate groups into a single connected group.

Example: Union Operation

#include <iostream>
using namespace std;
int parent[5] = {0,1,2,3,4};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
void unite(int a, int b) { parent[find(a)] = find(b); }
int main() { unite(0,1); cout << "0 and 1 merged, same root now: " << (find(0)==find(1)); return 0; }

public class Main {
	static int[] parent = {0,1,2,3,4};
	static int find(int x) { return parent[x]==x ? x : find(parent[x]); }
	static void unite(int a, int b) { parent[find(a)] = find(b); }
	public static void main(String[] args) { unite(0,1); System.out.println("0 and 1 merged, same root now: " + (find(0)==find(1))); }
}

parent = [0,1,2,3,4]
def find(x):
    return x if parent[x] == x else find(parent[x])
def unite(a, b):
    parent[find(a)] = find(b)
unite(0,1)
print("0 and 1 merged, same root now:", find(0)==find(1))

#include <stdio.h>
int parent[5] = {0,1,2,3,4};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
void unite(int a, int b) { parent[find(a)] = find(b); }
int main() { unite(0,1); printf("0 and 1 merged, same root now: %d", find(0)==find(1)); return 0; }

Path Compression

After a find operation, path compression re-points every node visited along the way directly to the root it discovered, so the very next find on any of those nodes finishes almost immediately instead of retracing the same long chain.

Example: Path Compression

#include <iostream>
using namespace std;
int parent[5] = {0,0,1,2,3};
int find(int x) { if (parent[x]!=x) parent[x] = find(parent[x]); return parent[x]; }
int main() { find(4); cout << "After find(4), node 4 points directly at root: " << parent[4]; return 0; }

public class Main {
	static int[] parent = {0,0,1,2,3};
	static int find(int x) { if (parent[x]!=x) parent[x] = find(parent[x]); return parent[x]; }
	public static void main(String[] args) { find(4); System.out.println("After find(4), node 4 points directly at root: " + parent[4]); }
}

parent = [0,0,1,2,3]
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]
find(4)
print("After find(4), node 4 points directly at root:", parent[4])

#include <stdio.h>
int parent[5] = {0,0,1,2,3};
int find(int x) { if (parent[x]!=x) parent[x] = find(parent[x]); return parent[x]; }
int main() { find(4); printf("After find(4), node 4 points directly at root: %d", parent[4]); return 0; }

Applications

DSU is the standard tool for tracking connectivity as edges are added one at a time (has this new edge connected two previously separate components?) and is the core building block behind Kruskal's minimum spanning tree algorithm.

Example: Applications

#include <iostream>
using namespace std;
int main() {
	cout << "DSU tracks connectivity as edges are added -- the core building block behind Kruskal's algorithm";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("DSU tracks connectivity as edges are added -- the core building block behind Kruskal's algorithm");
	}
}

print("DSU tracks connectivity as edges are added -- the core building block behind Kruskal's algorithm")

#include <stdio.h>
int main() {
	printf("DSU tracks connectivity as edges are added -- the core building block behind Kruskal's algorithm");
	return 0;
}

Disjoint Set Union DSU

What is DSU

Find Operation

Union Operation

Path Compression

Applications

Chapter Quiz — Complete all 7 topics to unlock

Login to run this code