PrevNext
Somewhat Frequent
 0/16

Disjoint Set Union

Authors: Benjamin Qi, Andrew Wang, Nathan Gong

Contributor: Michael Cao

The Disjoint Set Union (DSU) data structure, which allows you to add edges to a graph and test whether two vertices of the graph are connected.

Edit This Page

Focus Problem – try your best to solve this problem before continuing!

Resources

Resources
CF EDU

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

C++

Resources
Benq (from KACTL)

Below is an implementation of a DSU. It utilizes small-to-large merging and path compression to quickly perform union find. sizes[x] stores the size of xx's component, and parents[x] stores the parent of xx (equal to xx if it is the representative).

#include <bits/stdc++.h>
using namespace std;
class DisjointSets {
private:
vector<int> parents;
vector<int> sizes;
public:
DisjointSets(int size) : parents(size), sizes(size, 1) {

Java

import java.util.*;
public class DisjointSets {
int[] parents;
int[] sizes;
public DisjointSets(int size) {
parents = new int[size];
sizes = new int[size];
for (int i = 0; i < size; i++) {

Python

class DisjointSets:
def __init__(self, size: int) -> None:
self.parents = [i for i in range(size)]
self.sizes = [1 for _ in range(size)]
def find(self, x: int) -> int:
""":return: the "representative" node in x's component"""
if self.parents[x] == x:
return x
self.parents[x] = self.find(self.parents[x])

As the implementation is quite simple, you may prefer to use this in place of DFS for computing connected components.

Solution - Focus Problem

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 O(NQ)\mathcal{O}(NQ) time, which is too slow, motivating us to use union find.

By representing the graph with the union find data structure that was just implemented above, we can use its methods to both unite vertices and check if two vertices uiu_i and viv_i are in the same connected component using only O(α(N))\mathcal{O}(\alpha(N)) amortized time.

This reduces the overall time complexity to O(Qα(N))\mathcal{O}(Q \alpha(N)), which is a substantial improvement and allows us to pass all test cases.

Implementation

Time Complexity: O(Qα(N))\mathcal{O}(Q \alpha(N))

C++

#include <bits/stdc++.h>
using namespace std;
Code Snippet: DSU (Click to expand)
int main() {
int node_num, query_num;
cin >> node_num >> query_num;
DisjointSets dsu(node_num);

Java

import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Kattio io = new Kattio();
int size = io.nextInt();
int queryNum = io.nextInt();
DisjointSets dsu = new DisjointSets(size);

Python

Code Snippet: DSU (Click to expand)
size, query_num = [int(i) for i in input().split()]
dsu = DisjointSets(size)
for _ in range(query_num):
q_type, u, v = [int(i) for i in input().split()]
if q_type == 0:
dsu.unite(u, v)
else:
print(1 if dsu.connected(u, v) else 0)

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
Old SilverEasy
Show TagsDSU
CSANormal
Show TagsDSU
CFNormal
Show TagsDSU

Harder

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

StatusSourceProblem NameDifficultyTags
CSESHard
Show TagsDSU, Merging
GoldHard
Show TagsDSU, Merging, Sorted Set
Old GoldHard
Show TagsDSU
onlinejudge.orgHard
Show TagsDSU
Baltic OIVery Hard
Show TagsDSU
GoldVery Hard
Show TagsDSU
PlatinumVery 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