Disjoint Set Union

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.

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

Copy
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

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

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

Java

Copy
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

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