Disjoint Set Union

C++

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

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

Copy
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

Copy
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 x
		self.parents[x] = self.find(self.parents[x])

C++

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

Copy
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

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