【数据结构】并查集的概念与实现

并查集（Union、Find、Set）支持两个操作：合并两个集合、查找：判断两个元素是否在一个集合。

用一个与n等长的数组存储每个结点的父结点：

int father[n];

1	int father[n];

初始化，先令它们属于各自不同的集合，父结点都是自己：

for(int i = 1; i <= n; i++)
  father[i] = i;

1 2	for(int i = 1; i <= n; i++) father[i] = i;

查找：不断找父结点直到father[x] = x，递推或者递归方法都可以

int findFather(int x) {
  while(x != father[x])
    x = father[x];
  return x;
}

//或者递归
int findFather(int x) {
  if(x == father[x]) return x;
  else return findFather(father[x]);
}

int findFather(int x) {

while(x != father[x])

x = father[x];

return x;

}

//或者递归

int findFather(int x) {

if(x == father[x]) return x;

else return findFather(father[x]);

}

合并两个集合：找到a和b的根结点，如果根结点不同，就把其中一个的最高处的根结点的父亲设为另一个根结点

void Union(int a, int b) {
  int faA = findFather(a);
  int faB = findFather(b);
  if(faA != faB)
    father[faA] = faB;
}

void Union(int a, int b) {

int faA = findFather(a);

int faB = findFather(b);

if(faA != faB)

father[faA] = faB;

}

*对findFather函数进行路径压缩：

按原先的写法（递推写法）先获得根结点root
重新从x开始走一遍寻找根结点的过程，把路径上经过的所有结点的父亲全部改为根结点root

int findFather(int x) {
  int a = x;
  while(x != father[x])
    x = father[x];
  while(a != fahter[a]) { //路径压缩代码，可以省略
    int z = a;
    a = father[a];
    father[z] = x;
  }
  return x;
}

int findFather(int x) {

int a = x;

while(x != father[x])

x = father[x];

while(a != fahter[a]) { //路径压缩代码，可以省略

int z = a;

a = father[a];

father[z] = x;

}

return x;

}

如果判定条件是两个人有共同喜欢的课程，可以开一个数组course[1000]，1000为课程数，course[t]表示任意一个喜欢t课程的人的编号，这样的话，如果course[t] == 0说明当前读入的这个课程就他自己一个人喜欢，那么就令course[t] = i，他自己就是喜欢课程t的人的编号。findFather(course[t])就是这个人所在的社交网络的根结点，只需要合并当前读入的人的编号i和findFather(course[t])，表示把这两个人合并到了同一个圈子。

如果要统计一共有多少个圈子，只需要遍历一遍1~n，把它们的父结点对应的isRoot数组++，那么isRoot[i] = j表示以i为父结点的社交圈子中有j个人~~~

如果两个人之间不是可传递的关系，可以用一个二维数组enemy[a][b] = enemy[b][a] = 1存储a和b之间是否有关系。

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版