Disjoint_set_union.sublime-snippet

<snippet>
	<content><![CDATA[
struct DSU {

	vector<int> par, rnk, sz;
	int c;

	DSU(int n) : par(n + 1), rnk(n + 1, 0), sz(n + 1, 1), c(n) {
		for (int i = 1; i <= n; ++i) par[i] = i;
	}

	int find(int i) {
		return (par[i] == i ? i : (par[i] = find(par[i])));
	}

	bool same(int i, int j) {
		return find(i) == find(j);
	}

	int get_size(int i) {
		return sz[find(i)];
	}

	int count() {
		return c;   
	}

	int Union(int i, int j) {
		if ((i = find(i)) == (j = find(j))) return -1;
		else --c;
		if (rnk[i] > rnk[j]) swap(i, j);
		par[i] = j;
		sz[j] += sz[i];
		if (rnk[i] == rnk[j]) rnk[j]++;
		return j;
	}
};
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>Disjointsetunion</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>