# 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.

### Prerequisites

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 |

### Optional: DSU Complexity Proofs

## 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 $x$'s component,
and `parents[x]`

stores the parent of $x$ (equal to $x$ 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 xself.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 $\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 $u_i$ and $v_i$ are in the same connected component using only
$\mathcal{O}(\alpha(N))$ amortized time.

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

## Implementation

**Time Complexity:** $\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."

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 | |||

CF | 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 | |||

Gold | Hard | ## Show TagsDSU, Merging, Sorted Set | |||

Old Gold | Hard | ## Show TagsDSU | |||

onlinejudge.org | Hard | ## Show TagsDSU | |||

Baltic OI | Very Hard | ## Show TagsDSU | |||

Gold | Very Hard | ## Show TagsDSU | |||

Platinum | 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!