PrevNext
Somewhat Frequent
 0/10

Disjoint Set Union

Authors: Benjamin Qi, Michael Cao, Andrew Wang

The Disjoint Set Union (DSU) data structure allows you to add edges to an initially empty graph and test whether two vertices of the graph are connected.

Focus Problem – read through this problem before continuing!

Resources

Resources
CSAboth optimizations, diagrams
PAPSboth optimizations, no diagrams
CPHsmall to large, diagrams
IUSACOpath compression, diagrams
TCdiagrams

Implementations

As the implementation is quite simple, you may prefer to use this in place of DFS for computing connected components.

C++

Check PAPS for the explanation. e[x] contains the negation of the size of xx's component if xx is the representative of its component, and the parent of xx otherwise.

Resources
Benq (from KACTL)
1struct DSU {
2 vi e; void init(int N) { e = vi(N,-1); }
3 // get representive component, uses path compression
4 int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
5 bool sameSet(int a, int b) { return get(a) == get(b); }
6 int size(int x) { return -e[get(x)]; }
7 bool unite(int x, int y) { // union by size
8 x = get(x), y = get(y); if (x == y) return 0;
9 if (e[x] > e[y]) swap(x,y);
10 e[x] += e[y]; e[y] = x; return 1;

Java

This implementation assumes that p is an array that starts such that p[i] = -1 for every 0<=i<n0 <= i < n.

1public static int disjoint[]; //0 indexed
2public static int size[];
3//finds the "representative" node in a's component
4public static int find(int v) {
5 if (disjoint[v] == -1) {
6 return v;
7 }
8 disjoint[v] = find(disjoint[v]);
9 return disjoint[v];
10}

Focus Problem Solution

Focus Problem – read through this problem before continuing!

The solution below is more verbose than some of the templates above. Use whichever implementation you are most comfortable with.

C++

1#include <bits/stdc++.h>
2
3using namespace std;
4
5// sz[i] = size of component i, defaults to 1
6// pa[i] = parent of component i. If i is the root component, then pa[i] = i.
7int sz[200000], pa[200000];
8
9int get(int x) {
10 return x == pa[x] ? x : pa[x] = get(pa[x]);

Java

1import java.io.*;
2import java.util.*;
3
4public class Main {
5 public static int disjoint[]; //0 indexed
6 public static int size[];
7 public static int find(int v) {
8 if (disjoint[v] == -1) {
9 return v;
10 }

Problems

Standard

You should already be familiar with the DFS / Binary Search solutions to "Wormhole Sort" and "Moocast."

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
GoldEasyExternal Sol
GoldEasy
SilverEasy
Show Tags

DSU

External Sol
GoldEasy
Show Tags

DSU

External Sol
CSANormalCheck CSA

Harder

Don't worry about solving these if this is the first time you've encountered DSU.

StatusSourceProblem NameDifficultyTagsSolution
Baltic OIVery Hard
GoldVery Hard
Show Tags

DSU

External Sol
PlatVery Hard
Show Tags

DSU

Module Progress:

Give Us Feedback on Disjoint Set Union!

PrevNext