并查集

并查集的作用

• 检查图中是否存在环

并查集的流程

• 设定一个集合，叫并查集
• 往集合里面添加边，怎么添加呢？取边的起点和终点，判断两点是否都在集合里面。如果都在，则出现了环，如果不在，则将两个点放入集合中。
• 继续添加下一条边，直到没有边。如果最后都没有找到环，就是图中不存在环。

并查集的构造

并查集构造的三个动机：

• 能够表示点加入集合的不同状态；
• 方便查找点是否存在于集合中；
• 方便两个不同的集合进行合并。

根数组:

为了满足上述三点，于是便有人想出了并查集算法，想出了用根数组：parent实现并查集。

• parent[i]：表示第i个点的父节点。
• parent的初始化：parent[i] = i; 或 parent[i] = -1;

表示点加入集合的不同状态:

• 根数组用树的结构去表示点的状态。为什么用树呢？因为并查集算法就是为了检查环的存在，所以一旦有环的存在就会被判定为异常，即并查集无需表示环，而无环的连通图就是树。
• 有了数组parent[i]，就能根据父节点构造出森林出来，位于同一棵树的点自然属于同一集合。

查找点是否存在于集合:

• 并查集算法用根代表某一个集合。如果两个点的根一样，则表明两个点处于同一棵树上，即两个点同处于它们的根所代表的集合中。
• 而查找根的方法我们可以轻易根据数组parent实现，只需要一层一层的用父节点往上循环，直到根节点。
• 那么，如何判断是否为根节点呢？因为根节点从未加入其他节点，所以根据初始化条件的不同，根节点的 parent[i] = i; 或 parent[i] = -1; 这就是初始化的目的。

集合的合并:

• 既然，我们根据树和根节点来作为集合的判断依据，那么，如果我们要合并集合a和集合b，其实就是合并树a和树b。所以我们只需要将树a的根指向树b的根，或者将树b的根指向树a就可以了。

代码实现：

#include <iostream>
#include <cstring>

#define MAXL 10 // 定义根数组大小

using namespace std;

int parent[MAXL];

int Find(int x) {
	int t = x;
	while (parent[t] != -1) {
		t = parent[t]; // 一直向上递归找到根节点
	}
	return t;
}

int Join(int x, int y) {
	int parent_x = Find(x);
	int parent_y = Find(y);
	if (parent_x != parent_y) {
		parent[parent_x] = parent_y; // parent[parent_y] = parent_x也可
		return 1; // 表示无环，经合并到一个集合
	}
	return 0; // 表示有环
}

int main() {
	memset(parent, -1, sizeof(parent)); // 初始化所有节点的parent为-1

	int edge[7][2] = { {0, 1}, {1, 2}, {2, 3}, {4, 5}, {5, 6}, {1, 4}, {1, 6} };

	bool flag = true;

	for (int i = 0; i < 7; i++) { // 将每一条边放进集合
		int x = edge[i][0];
		int y = edge[i][1];
		if (Join(x, y) == 0) {
			cout << "有环" << endl;
			flag = false;
			break; // 直接退出
		}
	}
	
	if (flag) {
		cout << "无环" << endl;
	}

	return 0;
}

按秩合并

在集合合并的时候，在极端情况下会出现 0-1 1-2 2-3 3-4…… 这样一直让树的深度增加的情况。

这种情况就会导致点在查找根的时候，时间复杂度的增加。所以，为了降低算法的时间复杂度，有人提出了压缩路径和按秩合并的思想。

• 秩：这里指树的深度。算法使用 rank 数组来记录树的深度，如 rank[x] = y 表示 以 x 点为根结点的树的深度为 y。
• 算法未开始时，此时所有的树只有一个点，没有边，所以每个点的深度为 0，所以rank数组初始化为全0
• 算法开始合并时，比较要合并的两棵树的深度。
• 当两棵树的深度不一致时，让低的树的根指向高的树的根，这样新合并的树的高度就等于之前高的树的深度，而不会再度增加。
• 当两棵树的深度一致时，随便让一棵树的根指向另一棵树的根，这样新合并的树的高度就等于之前树的深度加上1，而不会增加很多。

代码实现:

#include <iostream>
#include <cstring>

#define MAXL 10 // 定义根数组大小

using namespace std;

int parent[MAXL];
int Rank[MAXL];

int Find(int x) {
	int t = x;
	while (parent[t] != -1) {
		t = parent[t]; // 一直向上递归找到根节点
	}
	return t;
}

int Join(int x, int y) { // 合并的时候进行秩的变化
	int parent_x = Find(x);
	int parent_y = Find(y);
	if (parent_x == parent_y) {
		return 0; // 表示有环，经合并到一个集合
	}
	else if (Rank[parent_x] > Rank[parent_y]) {
		parent[parent_y] = parent_x; // 让低秩的父节点指向高秩的节点，这样合并后秩不会增加
	}
	else if (Rank[parent_x] < Rank[parent_y]) {
		parent[parent_x] = parent_y; // 让低秩的父节点指向高秩的节点，这样合并后秩不会增加
	}
	else {
		parent[parent_x] = parent_y; // 两边秩一样，可任选一个做父节点，但要将秩+1
		Rank[parent_y]++; // 如果是 parent[parent_y] = parent_x;则 Rank[parent_x]++;
	}
	return 1; // 表示无环
}

int main() {
	memset(parent, -1, sizeof(parent)); // 初始化所有节点的parent为-1
	memset(Rank, 0, sizeof(Rank));

	int edge[7][2] = { {0, 1}, {1, 2}, {2, 3}, {4, 5}, {5, 6}, {1, 4}, {1, 6} };

	bool flag = true;

	for (int i = 0; i < 7; i++) { // 将每一条边放进集合
		int x = edge[i][0];
		int y = edge[i][1];
		if (Join(x, y) == 0) {
			cout << "有环" << endl;
			flag = false;
			break; // 直接退出
		}
	}
	
	if (flag) {
		cout << "无环" << endl;
	}

	return 0;
}