Disjoint Set Union
Authors: Benjamin Qi, Andrew Wang, Nathan Gong
Contributor: Michael Cao
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.
Prerequisites
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 | |||
Implementation
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) | ||||
#include <bits/stdc++.h>using namespace std;struct DSU {vector<int> e;DSU(int N) { e = vector<int>(N, -1); }// get representive component (uses path compression)int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
Java
import java.util.*;public class DisjointSets {int[] parents; // 0-indexedint[] sizes;public DisjointSets(int size) {sizes = new int[size];parents = new int[size];Arrays.fill(sizes, 1);
Python
class DisjointSets:def __init__(self, size: int) -> None:self.parents = [-1 for _ in range(size)]self.sizes = [1 for _ in range(size)]# finds the "representative" node in a's componentdef find(self, x: int) -> int:if self.parents[x] == -1:return xself.parents[x] = self.find(self.parents[x])
Solution - Focus Problem
Time Complexity:
Without union find, we would have to represent the graph with an adjacency list and use flood fill to calculate connected components. This approach takes time, which is too slow, motivating us to use union find.
By representing the graph with the union find data structure, we can use its methods to both unite vertices and check if two vertices and are in the same connected component using only time. This reduces the overall time complexity to , which is a substantial improvement and allows us to pass all test cases.
C++
#include <bits/stdc++.h>using namespace std;struct DSU {vector<int> e;DSU(int N) { e = vector<int>(N, -1); }// get representive component (uses path compression)int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
Java
import java.io.*;import java.util.*;public class Main {private static class DisjointSets {int[] parents; // 0-indexedint[] sizes;public DisjointSets(int size) {sizes = new int[size];parents = new int[size];
Python
class DisjointSets:def __init__(self, size: int) -> None:self.parents = [-1 for _ in range(size)]self.sizes = [1 for _ in range(size)]# finds the "representative" node in a's componentdef find(self, x: int) -> int:if self.parents[x] == -1:return xself.parents[x] = self.find(self.parents[x])
Problems
Standard
You should already be familiar with the DFS / Binary Search solutions to "Wormhole Sort" and "Moocast."
| Status | Source | Problem Name | Difficulty | Tags | |
|---|---|---|---|---|---|
| CSES | Easy | Show TagsDSU | |||
| Gold | Easy | Show TagsDSU | |||
| Gold | Easy | Show TagsDSU | |||
| Silver | Easy | Show TagsDSU | |||
| Gold | Easy | Show TagsDSU | |||
| Old Silver | Easy | Show TagsDSU | |||
| CSA | Normal | Show TagsDSU |
Harder
Don't worry about solving these if this is the first time you've encountered DSU.
| Status | Source | Problem Name | Difficulty | Tags | |
|---|---|---|---|---|---|
| CSES | Hard | Show TagsDSU, Merging | |||
| Old Gold | Hard | Show TagsDSU | |||
| onlinejudge.org | Hard | Show TagsDSU | |||
| Baltic OI | Very Hard | Show TagsDSU | |||
| Gold | Very Hard | Show TagsDSU | |||
| 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!