DSU

dsu.cpp

const int maxn = 1e5 + 5;

struct Dsu {
	struct Node {
		int val, fa;
	} t[maxn];

	void init(int sz) {
		for (int i = 0; i < n; i++)
			t[i].val = 1, t[i].fa = i;
	}

	int root(int x) {
		if (t[x].fa == x) return x;
		else return t[x].fa = root(t[x].fa);
	}

	void unite(int x, int y) {
		int fx = root(x);
		int fy = root(y);
		if (fx > fy) std::swap(fx, fy);
		t[fy].fa = fx;
		t[fx].val += t[fy].val;
	}

	int query(int x) {
		return t[root(x)].val;
	}
} dsu; // call init() before any further operation