视频地址 ：https://www.bilibili.com/video/av38498175?p=1
1 ，并查集的构造
① 设定一个集合，叫并查集，即 Disjoint Set，功能是检查 图中 是否出现了 环
② 往集合里面添加边，怎么添加呢。取边的起点和终点，判断两点是否都在集合里面,
如果都在，则出现了环，如果不在，将两个点 放入集合中。
③ 继续添加下一条边，如果没有边了，还没有找到环，就是没有环了
二，数组以树的形式实现
上面所讲的就是基本的思想了，下面讲如何具体实现
① 由于集合操作并不方便，所以便设法使用数组实现
② 由于上面所说的添加边 可以看成是一组点的集合 连接 另外一组点的集合，所以我们只要随便让集合的某一点 连接 另外一个集合的任意一点 就行了，
这样就可以让所有点处于连通状态
③ 基于上述所讲，我们可以将点以树的形式连接，为什么是树呢？因为集合中没有环，所以最后画出来的图形就是树了。
④ 由于连接的随意性， 这种连接方式，并不能正确表示一张图，只是能表示所有点是连接在一起的，且这种图画出来是树的形式。
⑤ 所以，我们可以构造一个 parent 数组，什么意思呢 ？ 就是 parent[x]=y, 指 x 的父节点是 y ,
为什么要 定义一个父节点呢？ 定义父节点的意思是 你可以通过父节点找到这个集合的根 ，根就是 所有点 都由 这个点 出发得到的。
那么，为什么要找到这个根呢？ 即这样做的优点。
优点1，在添加边的时候，可以通过查找 边上两个点的根结点是否存在，是否相同，达到判断两个点是否在之前的集合中出现过的效果
如图：想要添加左边 2-3 这条边，首先要判断边的两个点是否都在右边出现过。
如 2 的 父节点为 0，3 的父节点为 -1，即没有，所以并没有都出现过，只有一点出现过，
所以还没有环出现，可以添加边了。
优点2，可以在 加边 时减少树的深度，之后查找 根节点时就可以减少步骤
先看右边 3-4 这条边，他想加入左边的集合，怎么加呢？
在实际的图中，3 是连接着 2 的，但如果让 3 的父节点为 2，就让树的深度直接加了两层，
但如果让 3 的父节点为 0 深度增加了一层，即parent[0]=3 ,[且这样并不会影响到第一个优点。(｡￫‿￩｡)
接下来就是看代码了
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h> #define VERTICES 6 int find_root(int x, int parent[]) // 找到根节点 { int x_root = x; while (parent[x_root] != -1) { x_root = parent[x_root]; } return x_root; } int union_vertices(int x, int y, int parent[]) // 让两个集合合并 { int x_root = find_root(x, parent); int y_root = find_root(y, parent); if (x_root == y_root) return 0; else { parent[x_root] = y_root; return 1; } } int main(void) { int parent[VERTICES] = { 0 }; memset(parent, -1, sizeof(parent)); // 初始化 int edges[6][2] = { {0,1},{1,2},{1,3},{2,4},{3,4},{2,5} }; // 边集 for (int i = 0; i < 6; i++) { int x = edges[i][0]; int y = edges[i][1]; if (union_vertices(x, y, parent) == 0) { printf("Cycle detected! "); system("pause"); exit(0); } } printf("No cycle found. "); system("pause"); return 0; }
三，压缩路径
且看我上面优点 2 这一句 “但如果让 3 的父节点为 0 深度增加了一层” ，其实如果但如果让 0 的父节点为 3 深度就没有增加了
之前的代码中，我们这一步那个时那个的父节点我们并没有对此做一个判断，来判断哪一个成为 父节点 树的深度会更少。
这样子就有一个问题，如果一直是
0-1 1-2 2-3 3-4 这样子就会让树的深度一直增加，这样就会让 find_root 函数时间复杂度在最坏的情况下达到 o(n) ,即每个点都要查找。
所以，我们使用 rank 数组来记录 树的深度，如 rank[x]=y 表示 以 x 点为根结点的话，树的深度为 y
如图：现在有两颗树（并查集以树的形式）
要在添加一条边 x-y,
其中，x 的根节点为 Rx,y 的根节点为 Ry, 他们的根节点并不相同，所以没有环，可以加边，
那么我们就可以通过比较 rank[Rx] 与 rank[Ry] 来决定谁是谁的父节点。
优化后的代码实现：
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h> #define VERTICES 6 int find_root(int x, int parent[]) // 找到根节点 { int x_root = x; while (parent[x_root] != -1) { x_root = parent[x_root]; } return x_root; } int union_vertices(int x, int y, int parent[],int rank[]) // 让两个集合合并 { int x_root = find_root(x, parent); int y_root = find_root(y, parent); if (x_root == y_root) return 0; else { if (rank[x_root] > rank[y_root]) // 让 少的指向多 的 { parent[y_root] = x_root; } else if (rank[x_root] < rank[y_root]) parent[x_root] = y_root; else { parent[x_root] = y_root; // 这个随便可以 rank[y_root]++; } return 1; } } int main(void) { int parent[VERTICES] = { 0 }; int rank[VERTICES] = { 0 }; memset(rank, 0, sizeof(rank)); memset(parent, -1, sizeof(parent)); int edges[6][2] = { {0,1},{1,2},{1,3},{2,4},{3,4},{2,5} }; for (int i = 0; i < 6; i++) { int x = edges[i][0]; int y = edges[i][1]; if (union_vertices(x, y, parent,rank) == 0) { printf("Cycle detected! "); system("pause"); exit(0); } } printf("No cycle found. "); system("pause"); return 0; }
四，总结
要判定的图
流程图：
从图可以看出以下几点
① 当你添加的边中，有一点已经在集合中出现过了，根节点不会变，树的深度也是不会变，
② 你添加的第一条边父节点的出现是
由 第三个else ,决定的
else
{
parent[x_root] = y_root; // 这个随便可以
rank[y_root]++;
}
③，树所构成的图，与原来的图点的连接顺序基本不一样，
他只是保证了连通点是与原来一样的
over ！！！谢谢观看
=========== ========= ========= ======= ====== ====== ===== === == =
菩萨蛮 其三 唐 韦庄
如今却忆江南乐，当时年少春衫薄。骑马倚斜楼，满楼红袖招。
翠屏金屈曲，醉入花丛宿。此度见花枝，白头誓不归。