【算法】并查集

目录

• 并查集简介
• 主要思想
• 模板代码
• 进阶题目
• • 样例
  • • 样例输入
    • 样例输出
    • 样例解释
    • 解决思路
    • 代���

      并查集简介

      并查集是一种常见的数据结构

      主要用于解决"亲戚"问题，如 x x x 的亲戚为 y y y， y y y 的亲戚为 z z z，那么我们说 x x x 也是 z z z 的亲戚

      主要思想

      我们定义一个数组fa[x]表示 x x x 的父亲节点

      我们定义一种函数find(x)查询 x x x 所属路径的根节点

      有什么用呢？

      当 x x x 与 y y y 形成亲戚关系是，我们令 y y y 为 x x x 的祖先（即 find(x) ）的父亲

      最终会有亲戚关系的会形成如下的一条链

      所以 x x x， y y y， z z z， f f f 互为亲戚

      此时， f i n d ( x ) find(x) find(x) 为 f f f

      那么我们可以根据 find() 函数是否相同判断两个人是否为亲戚

      还有一个东西叫路径压缩

      如找 f i n d ( x ) find(x) find(x) 时，可以把 x x x 的父亲直接链接到祖先

      如图，红线指向压缩后的父亲

      路径压缩后时间复杂度将会减少，不会一次一次慢慢找了

      模板代码

      题目链接：P1551 亲戚

      #include#define ll long long#define endl '\n'using namespace std;int n,m,p,x,y,f[5005];int find(int x){ //找x的祖先if(f[x]==x) return x; else return f[x]=find(f[x]); // 路径压缩}int main(){scanf("%d%d%d",&n,&m,&p);for(int i=1;iscanf("%d%d",&x,&y);f[find(x)]=find(y); //x的祖先的父亲链接到y的祖先}for(int i=1;iscanf("%d%d",&x,&y);if(find(x)==find(y)) cout //并查集模板（找x的祖先）if(f[x]==x) return x;else return f[x]=find(f[x]); //路径压缩}int main(){scanf("%d%d",&n,&m);for(int i=1;icinc; scanf("%d%d",&x,&y);if(c=='F') //如果x于y为朋友关系f[find(x)]=find(y); //同模板代码else {f[find(x)]=find(y+n); //x的祖先与y的敌人相连f[find(x+n)]=find(y); //x的敌人的祖先于y的祖先相连}}for(int i=1;iif(a[find(i)]==0) ans++; //如果i的祖先所属的链没有出现，那么结果+1a[find(i)]=1; //i的祖先所属的链出现了，记录}printf("%d",ans);return 0;}