Disjoint Set Union

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.

struct DSU {
	vi e; void init(int N) { e = vi(N,-1); }
	// get representive component, uses path compression
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // union by size
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};

Java

This implementation assumes that disjoint is an array that starts such that disjoint[i] = -1 for every $0 <= i < n$.

public static int disjoint[]; //0 indexed
public static int size[];
//finds the "representative" node in a's component
public static int find(int v) {
	if (disjoint[v] == -1) {
		return v;
	}
	disjoint[v] = find(disjoint[v]);
	return disjoint[v];
}

C++

#include <bits/stdc++.h>

using namespace std;

// sz[i] = size of component i, defaults to 1
// pa[i] = parent of component i. If i is the root component, then pa[i] = i.
int sz[200000], pa[200000];

int get(int x) {
	return x == pa[x] ? x : pa[x] = get(pa[x]);

Java

import java.io.*;
import java.util.*;

public class Main {
	public static int disjoint[]; //0 indexed
	public static int size[];
	public static int find(int v) {
		if (disjoint[v] == -1) {
			return v;
		}