并查集

并查集

struct DSU {
	std::vector<int> p, siz;
	int num;

	DSU() {}
	DSU(int n) {
		init(n);
	}

	void init(int n) {
		num = n;
		p.resize(n);
		std::iota(p.begin(), p.end(), 0);
		siz.assign(n, 1);
	}

	int find(int u) {
		if (u != p[u]) {
			p[u] = find(p[u]);
		}
		return p[u];
	}

	bool same(int u, int v) {
		return find(u) == find(v);
	}

	bool merge(int u, int v) {
		int fa_u = find(u), fa_v = find(v);
		if (fa_u == fa_v) {
			return false;
		}
		siz[fa_u] += siz[fa_v];
		p[fa_v] = fa_u;
		return true;
	}

	int size(int u) {
		return siz[find(u)];
	}

};