Somewhat Frequent
0/10

# 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
CSAboth optimizations, diagrams
PAPSboth optimizations, no diagrams
CPHsmall to large, diagrams
IUSACOpath compression, diagrams
TCdiagrams
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 $x$'s component if $x$ is the representative of its component, and the parent of $x$ otherwise.

Resources
Benq (from KACTL)
1struct DSU {2    vi e; void init(int N) { e = vi(N,-1); }3    // get representive component, uses path compression4    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 size8        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 < n$.

1public static int disjoint[]; //0 indexed2public static int size[];3//finds the "representative" node in a's component4public 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 16// pa[i] = parent of component i. If i is the root component, then pa[i] = i.7int sz, pa;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 indexed6    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