并查集（基础）

fsp_luogu · 2024-04-13 16:51:29 · 算法·理论

并查集（基础）

1.什么是并查集？

并查集，顾名思义就是“合并”或“查询”集合。这是一个图论的基本算法。

2.并查集可以用来干什么？

1. 判断两个元素是否在同一个集合中：分别查找他们的根节点， 如果他们的根节点是相同的，那么这两个元素在同一个集合中。

2. 合并两个集合： 分别查找两个集合的根节点，将这两个根节点连接起来。

3. 在查找的同时提高效率： 具体见代码。

   3.代码如何实现？

4. 查找：

   int find(int x){
   if(x==fa[x])return x;
   else
   return  fa[x]=find(fa[x]);
       //这一句代码可以将在节点x到根节点路径上所有节点的父节点变成根节点
   }

   可以看出来这个函数是使用递归实现的。

5. 判断两个元素是否在同一个集合中:

   bool judge(int x,int y){
   int p1=find(x);
   int p2=find(y);//查找两个节点的根节点
   return p1==p2;// 这两个元素的跟节点是否是一样的
   }

6. 合并两个集合:

   int merge(int x,int y){
   int p1=find(x);
   int p2=find(y);
   if(p1!=p2)fa[p1]=p2;// 这里的fa[n]存的是节点n的父节点
       } 

这是我的第一篇专栏，感谢大家多多点赞！