Somewhat Frequent
0/14

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 $x$'s component if $x$ is the representative of its component, and the parent of $x$ 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-indexed	int[] 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 component	def find(self, x: int) -> int:		if self.parents[x] == -1:			return x		self.parents[x] = self.find(self.parents[x])

Solution - Focus Problem

Time Complexity: $\mathcal{O}(Q \log ^*N)$

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 $\mathcal{O}(NQ)$ 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 $u_i$ and $v_i$ are in the same connected component using only $\mathcal{O}(\log^*N)$ time. This reduces the overall time complexity to $\mathcal{O}(Q \log ^*N)$, 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-indexed		int[] 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 component	def find(self, x: int) -> int:		if self.parents[x] == -1:			return x		self.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."

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsDSU
GoldEasy
Show TagsDSU
GoldEasy
Show TagsDSU
SilverEasy
Show TagsDSU
GoldEasy
Show TagsDSU
Old SilverEasy
Show TagsDSU
CSANormal
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
Old GoldHard
Show TagsDSU
onlinejudge.orgHard
Show TagsDSU
Baltic OIVery Hard
Show TagsDSU
GoldVery Hard
Show TagsDSU
PlatVery Hard
Show TagsDSU

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!