图论知识：并查集（基本写法，无压缩）
既然研究到了最小生成树，那就必须得谈一谈克鲁斯卡尔算法了。既然谈到了克鲁斯卡尔算法，那就必须先把并查集弄清楚！
推荐博客：https://blog.****.net/w1085541827/article/details/52076481
现在先给出这样一个图，然后给定两个结点，然你判断它们是否在同一个子网中。
比如图中，4、5结点是在一个子网中的。
我们就利用这一道题来实现一下并查集。
并查集的核心思想：用一个parent数组记录这个结点的直接上级，如果一个结点的直接上级是自己，那么我们称这个结点为boss结点。然后，我们这题的目标就是，把所有相邻结点的boss置为同一个结点，那么判断结点a与结点b是否属于同一子网的问题就转换成，判断结点a和结点b的boss结点是不是一个结点！
这个道理其实很简单，比如，就拿家族关系来举例。我的直接上级是我爸爸，我爸爸的直接上级是我爷爷（暂时不考虑爷爷的爸爸，将爷爷视为boss结点）。那么我的boss结点实际上就是爷爷。
然后，我表弟的直接上级是我叔叔（爸爸的弟弟），我叔叔的直接上级也是我爷爷，所以我表弟的boss结点也是我爷爷！
那么别人问我：“你和你表弟是一家人吗？”
我可以回答：“是啊，因为我和我表弟拥有共同的boss结点–爷爷，所以我们是一家人！”
参考代码：
/*
测试用例：
7 4
1 2
2 3
2 6
4 5
*/
#include<iostream>
using namespace std;
const int maxn = 50;
int e[maxn][maxn]; //给定一个无向图，判断其中某两个顶点是否在一个网中
int parent[maxn]; //下标代表元素自己，parent代表它的直接上级，而不是boss！
int n, m; //n代表顶点数，m代表边数
//构造并查集
int getBoss(int x) //查找x节点的boss节点，用递归好写
{
if(parent[x] == x) //边界：上级等于自己，那么我自己就是boss节点
return x;
return getBoss(parent[x]); //返回我上级的boss节点即可
}
void merge(int x, int y) //将两个结点合并到一起，即boss变成一样（并！）
{
int boss_x = getBoss(x);
int boss_y = getBoss(y);
parent[boss_x] = boss_y; //就把x的boss的boss变成y的boss即可（反之亦然）
}
bool judge(int x, int y) //判断是否为同一个boss
{
int boss_x = getBoss(x);
int boss_y = getBoss(y);
return boss_x == boss_y;
}
//--------------------------------------
int main()
{
cin >> n >> m;
//输入无向图的边
for(int i = 1;i <= m;i++)
{
int a, b;
cin >> a >> b;
e[a][b] = 1; //无向图，双向的
e[b][a] = 1;
}
int node1, node2;
cout << "请输入您要查找的两个点：";
cin >> node1 >> node2;
//对parent数组进行初始化，每个人的初始上级都是自己
for(int i = 1;i <= n;i++)
parent[i] = i;
//根据邻接矩阵无向图，利用并查集构造彼此的关系
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
//如果两个结点有边相连，并且没有合并过，那么就merge起来！
if(e[i][j] == 1 && !judge(i, j))
{
merge(i, j); //两者的boss变成一样了！
}
}
}
//如果node1与node2不是同一个boss，那么他们就不在一个网内
if(judge(node1, node2))
{
cout << node1 << " 结点与 " << node2 << " 结点在同一个子网内" << endl;
}
else
{
cout << "他们不在一个子网内" << endl;
}
return 0;
}
一旦用到并查集的知识，那么构造并查集，即getBoss， merge，judge这三大函数一般是少不了的，其他代码就可以根据具体题意来更改了。暂时未考虑路径压缩的情况
运行结果：
运行结果2：