Resources Implementation Solution - Focus Problem Problems Standard Harder

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.

Edit This Page

Prerequisites

Silver - Depth First Search (DFS)

Resources Implementation Solution - Focus Problem Problems Standard Harder

Union Find

YS - Easy

Focus Problem – read through this problem before continuing!

Resources


CF	EDU: DSU	video explanation + problems for DSU
CSA	Disjoint Data Sets	both optimizations, diagrams
PAPS	11.1 - Disjoint Sets	both optimizations, no diagrams
CPH	15.2 - Union-Find	small to large, diagrams
IUSACO	10.6 - Disjoint-Set Data Structure	path compression, diagrams
TC	Disjoint Set Data Structures	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)	DSU

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

Source	Problem Name	Difficulty	Tags
CSES	Road Construction	Easy	Show Tags DSU
Gold	Closing the Farm	Easy	Show Tags DSU
Gold	Mootube	Easy	Show Tags DSU
Silver	Wormhole Sort	Easy	Show Tags DSU
Gold	Moocast	Easy	Show Tags DSU
Old Silver	Tractor	Easy	Show Tags DSU
CSA	Mountain Time	Normal	Show Tags DSU

Harder

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

Source	Problem Name	Difficulty	Tags
CSES	New Roads Queries	Hard	Show Tags DSU, Merging
Old Gold	Ski Course Rating	Hard	Show Tags DSU
onlinejudge.org	War	Hard	Show Tags DSU
Baltic OI	2016 - Park	Very Hard	Show Tags DSU
Gold	Favorite Colors	Very Hard	Show Tags DSU
Plat	Valleys	Very Hard	Show Tags DSU

Table of Contents

Disjoint Set Union

Prerequisites

Table of Contents

Resources

Optional: DSU Complexity Proofs

Implementation

Solution - Focus Problem

Problems

Standard

Harder

Module Progress:

Table of Contents

Disjoint Set Union

Prerequisites

Table of Contents

Resources

Optional: DSU Complexity Proofs

Implementation

Solution - Focus Problem

Problems

Standard

Harder

Module Progress:Not Started

Module Progress: