Disjoint Set Union
Authors: Benjamin Qi, Michael Cao, Andrew Wang
Prerequisites
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 |
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 's component if is the representative of its component, and the parent of otherwise.
Resources | |||
---|---|---|---|
Benq (from KACTL) |
struct DSU {vi e; void init(int N) { e = vi(N,-1); }// get representive component, uses path compressionint 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 sizex = 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 .
public static int disjoint[]; //0 indexedpublic static int size[];//finds the "representative" node in a's componentpublic 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 indexedpublic 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."
Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|
CSES | Easy | Show TagsDSU | ||||
Gold | Easy | Show TagsDSU | External Sol | |||
Gold | Easy | Show TagsDSU | ||||
Silver | Easy | Show TagsDSU | ||||
Gold | Easy | Show TagsDSU | ||||
CSA | Normal | Show TagsDSU | Check CSA |
Harder
Don't worry about solving these if this is the first time you've encountered DSU.
Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|
Old Gold | Hard | Show TagsDSU | External Sol | |||
Baltic OI | Very Hard | Show TagsDSU | ||||
Gold | Very Hard | Show TagsDSU | External Sol | |||
Plat | Very 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!