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

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-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:** $\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-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!