【模板】并查集——查询合并

适用场景

当程序涉及大量不交集“元素分类”，“类别合并”，“类别查询”时可以考虑使用并查集
但注意，不支持集合的分离与删除

并查集的原理

并查集通过维护一棵树实现。每个子节点都指向一个父节点，直到指向到“祖先”，每个节点对应着的“祖先”有且只有一个，而不同的“祖先”则对应着不同的集合。在查询时，只需迭代找到祖先；在添加新元素时，只需要把元素指向对应集合的一个父节点；在合并时，只需把一者的祖先指向另一者的祖先。

模板代码

int f[maxn];
int find(int i) {	//递归寻找i的祖先，并进行路径压缩
  if (i != f[i])
    f[i] = find(f[i]);
  return f[i];
}
void uni(int i, int j) {	//将y集合并入x的祖先旗下
	int x = find(i), y = find(j);
	if (x == y) return;
	f[y] = x;
}