代码

int par[max_n];  //父亲数组
int rank[max_n];  //树的高度

void init(int n) {    //初始化
	for (int i = 0; i < n; i++) {
		par[i] = i;
		rank[i] = 0;
	}
}

int find(int x) {  //查询树的根
	if (par[x] == x) return x;
	else {
		return par[x] = find(par[x]);
	}
}

void unite(int x, int y) {   //合并x,y所属的集合
	x = find(x);
	y = find(y);
	if (x == y) return;

	if (rank[x] < rank[y])  par[x] = y;
	else {
		par[y] = x;
		if (rank[x] == rank[y]) rank[x]++;
	}
}

bool same(int x, int y) {
	return find(x) == find(y);
}