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.

1struct DSU {
2    vi e; void init(int N) { e = vi(N,-1); }
3    // get representive component, uses path compression
4    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
5    bool sameSet(int a, int b) { return get(a) == get(b); }
6    int size(int x) { return -e[get(x)]; }
7    bool unite(int x, int y) { // union by size
8        x = get(x), y = get(y); if (x == y) return 0;
9        if (e[x] > e[y]) swap(x,y);
10        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$.

1public static int disjoint[]; //0 indexed
2public static int size[];
3//finds the "representative" node in a's component
4public static int find(int v) {
5    if (disjoint[v] == -1) {
6        return v;
7    }
8    disjoint[v] = find(disjoint[v]);
9    return disjoint[v];
10}

C++

1#include <bits/stdc++.h>
2
3using namespace std;
4
5// sz[i] = size of component i, defaults to 1
6// pa[i] = parent of component i. If i is the root component, then pa[i] = i.
7int sz[200000], pa[200000];
8
9int get(int x) {
10    return x == pa[x] ? x : pa[x] = get(pa[x]);

Java

1import java.io.*;
2import java.util.*;
3
4public class Main {
5    public static int disjoint[]; //0 indexed
6    public static int size[];
7    public static int find(int v) {
8        if (disjoint[v] == -1) {
9            return v;
10        }