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 p is an array that starts such that p[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;
        }