并查集

一、并查集是什么#

并查集用来“拉帮结派”，学术点来说，就是用来处理不相交集合的合并以及查找成员的集合归属的算法。主要有 union 和 find 两个操作，分别用来合并两个集合、查找成员集合归属。

二、什么思想#

首先，怎么区分各个集合？找集合中某个人作为老大，他就是这个集合的代表，想知道某个人在哪个集合中，找他的老大就好了。至于怎么找，我们定义一个上级数组 parent[]，用来存储每个对象的上级，一级一级往上找就好。

find 操作#

找成员 x 的老大，一级一级往上找，直到找到一个人，他的上级就是他自己。

int find(int x) {
	while(x != parent[x]) {
		x = parent[x];
	}
	return x;
}

union 操作#

将集合 A 和集合 B 合并，那么只需要让 A 的老大变成 B，或者 B 的老大变成 A 即可。

void union(int x,int y) { //让x和y变成一伙的
	int rootX = find(x);
	int rootY = find(y);
	parent[rootX] = rootY;
}

我们可以发现，这其实就是棵树 不过现在有了新问题：当树的高度过高，会导致 find 操作的时间成本很大，所以我们可以采用路径压缩的方法——当我们进行 find 操作时，会从下到上遍历每一个上级，那么我们可以边遍历，边让每个节点的上级直接变成老大，这样会使得树的高度直线下降。

int find(int x) {
	while(x != parent[x]) {
		x = find(parent[x]);
	}
	return x;
}