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
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)
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 p is an array that starts such that p[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 NameDifficultyTagsSolutionURL
CSESEasy
GoldEasyExternal Sol
GoldEasy
SilverEasy
Show Tags

DSU

GoldEasy
Show Tags

DSU

CSANormalCheck CSA

Harder

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

StatusSourceProblem NameDifficultyTagsSolutionURL
Old GoldHard
Show Tags

DSU

External Sol
Baltic OIVery Hard
GoldVery Hard
Show Tags

DSU

External Sol
PlatVery Hard
Show Tags

DSU

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!

Give Us Feedback on Disjoint Set Union!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext