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

Check PAPS for an 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-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])

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

## Solution - Focus Problem

**Time Complexity:** $\mathcal{O}(Q \alpha(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}(\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.

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;DSU dsu(node_num);

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

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

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

CF | Hard | ## Show Tags2SAT, DSU | |||

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!