PrevNext
Somewhat Frequent
 0/11

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
CF

video explanation + problems for DSU

CSA

both optimizations, diagrams

PAPS

both optimizations, no diagrams

CPH

small to large, diagrams

IUSACO

path compression, diagrams

TC

diagrams

Optional: DSU Complexity Proofs

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)
struct DSU {
vi e; void init(int N) { e = vi(N,-1); }
// get representive component, uses path compression
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool sameSet(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) { // union by size
x = get(x), y = get(y); if (x == y) return 0;
if (e[x] > e[y]) swap(x,y);
e[x] += e[y]; e[y] = x; return 1;
}
};

Java

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

public static int disjoint[]; //0 indexed
public static int size[];
//finds the "representative" node in a's component
public static int find(int v) {
if (disjoint[v] == -1) {
return v;
}
disjoint[v] = find(disjoint[v]);
return disjoint[v];
}

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++

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

Java

import java.io.*;
import java.util.*;
public class Main {
public static int disjoint[]; //0 indexed
public static int size[];
public static int find(int v) {
if (disjoint[v] == -1) {
return v;
}

Problems

Standard

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

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsDSU
GoldEasy
Show TagsDSU
GoldEasy
Show TagsDSU
SilverEasy
Show TagsDSU
GoldEasy
Show TagsDSU
CSANormal
Show TagsDSU

Harder

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

StatusSourceProblem NameDifficultyTags
Old GoldHard
Show TagsDSU
Baltic OIVery Hard
Show TagsDSU
GoldVery Hard
Show TagsDSU
PlatVery Hard
Show TagsDSU

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext