并查集入门
先推荐两个个人认为非常好的教程，可以对比以下再抉择看哪一个好理解。
这篇博客的内容来自B站一个非常棒的入门视频，个人在学习时整理成笔记发了出来。这个UP主的其它内容也通俗易懂，非常推荐！！
还有这个博客讲并查集入门也是非常通俗易懂，语言也是相当幽默，佩服佩服！
下面以并查集在查找图中是否存在环的问题入手，详细说明并查集的每一个步骤
一、并查集入门例题
例如有如下一个图（以下讨论都是无向图）。并查集可以检测图中是否存在环，如上图中有路径1->2->4->3-1，即存在一个环，我们的目的就是通过并查集检测该图中是否有环，有则输出true，没有环则输出flase
首先我们可以按任何顺序遍历该图上的边，比如我们首先选择了0->1这条边，这条边连接了两个点，即0号顶点和1号顶点，这两个顶点通过这条选出的红色边连接起来表示这两个顶点有联系，那么我们把这两个顶点放入同一个集合当中，如下图集合A。
然后我们继续选择上图中的边，比如我们选择了1->2这条边，通过下图选择的这条红色边可以把2号顶点和1号顶点连接起来，即2号顶点和1号顶点有联系，和上面的操作一样我们把2号顶点和1号顶点放入同一个集合当中，又因为1号顶点和0号顶点同属一个集合A，那么其实只要把2号顶点加入0号和1号顶点同属的集合A中即可。
继续选择图中的边，比如我们选择了3->4这条边，通过这条边4号顶点和3号顶点建立了联系，和上面操作一样把4号顶点和3号顶点放入同一个集合，3号顶点和4号顶点原先不属于任何集合，所以把它们放入一个新的集合B当中。
继续重复上述操作，假如选择的下一条边为1->3，通过这条边把1号顶点和3号顶点联系起来，通过这条边可知1号顶点和3号顶点应当同一个集合当中，但是此时1号顶点属于集合A，而2号顶点属于集合B，所以此时需要执行一个集合的合并操作，把集合A和集合B合并成一个新的集合C，如下图。
集合C的含义是在图上由这些点和它们之间的红色的边构成的子图是连通的，即可以从任意一点出发到达任何点，同时除了下图标记为红色的边，在集合C中任意再选两个顶点构成的边必定形成环如下图。
回到正题，选择了上图所示的红色边后，继续选择新的边，假如选择了2->4这条边，因为2号顶点属于集合C，同时4号顶点也属于集合C，即这两个点同属于一个集合！而我们知道在集合C中任意再选两个顶点构成的边必定形成环！，所以这就引出了并查集的核心思想：在图中不断选择边，通过被选择的边将边连接的两个顶点加入同一个集合，如此不断反复，这其中可能涉及集合的合并操作，当选择的边两端的点已经属于同一个集合时，此时可以得出结论该图中存在环！
二、并查集的代码思路
还记得该算法过程中有一步很重要的步骤，将下图通过1->3这条边，将集合A和集合B合并成集合C，如下图
并查集通过采用树的方式表示一个集合，如上图，可以将集合A用一棵树表示（也可以说是由这棵树的根节点表示，这点非常重要！），集合B用另外一棵树表示，当要合并为集合C的时候，只需要将其中一棵树的根节点作为另外一棵树的孩子即可，这样可以非常方便的实现集合的合并操作。下面详细说明如何实现上述操作。
我们定义了一个parent数组，令其长度和图中的顶点数一致，并且全部初始化为-1，使用该数组表示集合的树结构。比如我们设置parent[1] = 0, parent[2] = 0，表示1号顶点的父节点为0号顶点，2号顶点的父节点也为0号顶点，其中-1表示该顶点为独立的顶点，还没有父节点，也就是还不属于任何一个集合，如下图所示：
了解了parent数组的功能后，接下来分析如何实现并查集。和前面所讲的一样，先随机选择一条边，假设选择了0->1这条边，要把0号顶点和1号顶点加入同一个集合，只需要把0号顶点和1号顶点用一个树表示出来即可，谁是根节点都可以（暂时不考虑优化），这里假设我们使用1号顶点作为根节点，即设置parent[0] = 1表示0号顶点的父节点为1号顶点，如下图所示：
继续找下一条边，假设找到1->2这条边，然后我们需要把1号顶点和2号顶点放入一个集合，把1号顶点和2号顶点放在用一棵树上，可以随便选择用1号或者2号顶点作为根节点，假设我们选择1号顶点作为根节点，设置parent[2] = 1，即把2号顶点的父节点设置为1号顶点，如下图
继续选择边，假设选择了3->4这条边，那么只有把3号顶点和4号顶点用一棵树表示即可，这里设置parent[3] = 4，将4号顶点作为父节点，如下图
下一条被选择的边为1->3，只需要把1号顶点和3号顶点加入同一颗树即可，可以把3号顶点作为1号顶点的父节点，但是这样会使得树的高度比较高，不利于后续查找。还记得上面提过的一棵树代表的是一个集合，而这棵树实际上可以使用该树的根节点表示！！！所以合并两棵树只需要考虑两棵树的根节点1号顶点和4号顶点合并即可，假设执行parent[1] = 4，将4号节点作为父节点实现两棵树的合并。如下图
当使用根节点代表一棵树时，现在数据小可以直接看出3号点所在树的根节点为4号点，但是数据大时并不是那么直观，所以我们写一个函数root(i),该函数的功能为找到i号节点的根节点。root函数实现很简单，只需要不断向上一个节点迭代直到最后一个节点的父节点为-1表示该节点就是这棵树的根节点。
int find_root(int x, int parent[])
{
while (parent[x] != -1)
{
x = parent[x];
}
return x;
}
————————————————————————————————————————————
继续选择下一条边，假设下一条边为2->4，将2号顶点所在的树和4号顶点所在的树合并成一个树，我们先通过调用root(2)找到2号点所在的树的根节点为4号顶点，再调用root(4)找到4号顶点所在树的根节点也为4号顶点。由上面的讨论可知，在一个已经存在的集合中，任意取得除了生成该集合的点使用过的边（下图红色的边）外的任一一条边，都会使得图中出现一个环（有点拗口。。。）。所以算法运行到这里就发现了环，不需要再继续检测5号顶点。
Talk is cheap,show me the code!
通过上面的讨论，可以知道实现该算法需要两个关键步骤，一个为查找一个节点的根节点，假设这个函数为find_root()（ 就是上面说的root() ）,另一个为实现树的合并操作的函数union_tree()，上面说的够详细了，代码也不难，直接上代码。
#include "stdio.h"
#include "stdlib.h"
#define VERTICES 6
//顶点数
int find_root(int x, int parent[])
{
while (parent[x] != -1)
{
x = parent[x];
}
return x;
}
//合并x点和y点所在的树，返回1表示合并成功，返回0表示合并失败（即两个点本来就在同一个集合）
int union_tree(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()
{
int parent[VERTICES] = {0};
int edges[6][2] = {
{0, 1}, {1, 2}, {1, 3}, {2, 4}, {3, 4}, {2, 5}}; //存放6条边
//初始化parent数组
for (int i = 0; i < VERTICES; i++)
parent[i] = -1;
int i;
for (i = 0; i < 6; i++) //遍历每一条边，试图将该边连接的两个顶点加入一个集合
{
int x = edges[i][0];
int y = edges[i][1];
if (union_tree(x, y, parent) == 0)
{
printf("Cycle detected!\n");
break;
}
}
if (i == 6)//检测完了所有边，没有发现环
printf("No cycles found.\n");
system("pause");
return 0;
}
测试：上述代码中输入表示下图
修改edges数组，删除边2->4，同时修改相应的边数为5，输入为下图：
只需要把main函数修改一下即可
int main()
{
int parent[VERTICES] = {0};
int edges[5][2] = {
{0, 1}, {1, 2}, {1, 3}, {3, 4}, {2, 5}}; //存放5条边
//初始化parent数组
for (int i = 0; i < VERTICES; i++)
parent[i] = -1;
int i;
for (i = 0; i < 5; i++) //遍历每一条边，试图将该边连接的两个顶点加入一个集合
{
int x = edges[i][0];
int y = edges[i][1];
if (union_tree(x, y, parent) == 0)
{ //x,y两个顶点同属于一个集合，发现环
printf("Cycle detected!\n");
break;
}
}
if (i == 5) //检测完了所有边，没有发现环
printf("No cycles found.\n");
system("pause");
return 0;
}
三、并查集的优化
在上面union_tree函数中，如果合并的两个点同属于一个集合，直接返回合并失败必然是没有问题的，但是如果两个点属于不同的集合，合并时并没有考虑代表两个集合的树的深度，上面的代码只是简单的执行parent[x_root] = y_root；每次都让y成为父节点，这样可能会导致生成的这棵树深度会很大（退化树），这样执行find_root函数时要搜索的时间就会比较长了。
怎样做才能把树的深度尽量降低呢？首先增加一个辅助量，rank[]是一个数组，长度和图中点的个数一致，rank[x]的含义为以x为根的子树的深度，初始化所有点的rank为1！假设有下图这样一种情况，x，y分属不同集合，当合并时，我们不再固定x作为父节点，或者固定y作为父节点，而是考虑点x所属树的深度（其深度为rank[Rx],下图中rank[Rx] = 4），以及考虑点y所属树的深度（rank[Ry]，下图中rank[Ry]=2），将深度较大点所在树的根节点作为合并后的根节点，所以下图中将Ry连接到Rx上(因为rank[x]>rank[y])，这样合并后的树的深度不会增加。
所以修改后的代码如下（主要修改了union_tree函数）：
#include "stdio.h"
#include "stdlib.h"
#define VERTICES 6
//顶点数
int find_root(int x, int parent[])
{
while (parent[x] != -1)
{
x = parent[x];
}
return x;
}
//合并x点和y点所在的树，返回1表示合并成功，返回0表示合并失败（即两个点本来就在同一个集合）
int union_tree(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)
{ //x，y两个点同属于一个集合
return 0;
}
else if (rank[x_root] > rank[y_root])
{
parent[y_root] = x;
}
else if (rank[y_root] > rank[x_root])
{
parent[x_root] = y_root;
}
else if (rank[x_root == rank[y_root]])
{
parent[x_root] = y_root;
rank[y_root]++;
}
return 1;
}
int main()
{
int parent[VERTICES] = {0};
int rank[VERTICES] = {0};
int edges[6][2] = {
{0, 1}, {1, 2}, {1, 3}, {3, 4}, {2, 5}, {5, 4}};
//初始化parent,rank数组
for (int i = 0; i < VERTICES; i++)
{
parent[i] = -1;
rank[i] = 1;
}
int i;
for (i = 0; i < 6; i++) //遍历每一条边，试图将该边连接的两个顶点加入一个集合
{
int x = edges[i][0];
int y = edges[i][1];
if (union_tree(x, y, parent, rank) == 0)
{ //x,y两个顶点同属于一个集合，发现环
printf("Cycle detected!\n");
break;
}
}
if (i == 6) //检测完了所有边，没有发现环
printf("No cycles found.\n");
system("pause");
return 0;
}
还有一种优化方式。我们也可以修改find_root，函数来实现路径压缩。我们的目的是想让生成的树的深度尽可能小，可以考虑当执行find_root查找某一个点的根节点时，因为我们采用的是不断向上迭代寻找根节点，这必然经历了一条从当前节点到根节点的路径，当查找到根节点时，修改这条路径上的所有点的根节点为查到到的点，这样下次查找这些点的时候只需向上查找一次即可。比如find_root查找x的根节点，如下图经历了x->t4->t1->Rx，之后修改则形成下图右侧所示的新的树结构。
为了方便实现优化后的find_root()函数，这里将parent数组稍作修改，初始化parent[i] = i，即开始时每个节点的根节点都为自己，查找根节点时判断条件是if(parent[i]==i) return i
find_root代码实现：
int find_root(int x, int parent[])
{
if (parent[x] == x)
return x;
else
{
return parent[x] = find_root(parent[x], parent); //递归实现
}
}
所有代码（修改parent[i]初始化为i）：
#include "stdio.h"
#include "stdlib.h"
#define VERTICES 6
//顶点数
int find_root(int x, int parent[])
{
if (parent[x] == x)
return x;
else
{
return parent[x] = find_root(parent[x], parent); //递归实现
}
}
//合并x点和y点所在的树，返回1表示合并成功，返回0表示合并失败（即两个点本来就在同一个集合）
int union_tree(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)
{ //x，y两个点同属于一个集合
return 0;
}
else if (rank[x_root] > rank[y_root])
{
parent[y_root] = x;
}
else if (rank[y_root] > rank[x_root])
{
parent[x_root] = y_root;
}
else if (rank[x_root == rank[y_root]])
{
parent[x_root] = y_root;
rank[y_root]++;
}
return 1;
}
int main()
{
int parent[VERTICES] = {0};
int rank[VERTICES] = {0};
int edges[6][2] = {
{0, 1}, {1, 2}, {1, 3}, {3, 4}, {2, 5}, {5, 4}};
//初始化parent,rank数组
for (int i = 0; i < VERTICES; i++)
{
parent[i] = i;
rank[i] = 1;
}
int i;
for (i = 0; i < 6; i++) //遍历每一条边，试图将该边连接的两个顶点加入一个集合
{
int x = edges[i][0];
int y = edges[i][1];
if (union_tree(x, y, parent, rank) == 0)
{ //x,y两个顶点同属于一个集合，发现环
printf("Cycle detected!\n");
break;
}
}
if (i == 6) //检测完了所有边，没有发现环
printf("No cycles found.\n");
system("pause");
return 0;
}
输入
输出
the end!写的有些啰嗦。。。不知道有没有错误的地方，如果有还请指出！
通过这个例子算是基本了解了并查集，但是要熟悉运用还是得找些题练习以下。