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

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

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

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

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

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

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

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

  • 如果判定条件是两个人有共同喜欢的课程,可以开一个数组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、蓝桥杯、GPLT天梯赛、LeetCode题解离线版❤❤