题目详见:[【P3367】【模板】并查集] (https://www.luogu.org/problemnew/show/P3367)
这是一道裸的并查集题目(要不然叫模板呢) 废话不多说进入正题:
并查集通过一个一维数组来实现,本质上是维护一个森林。刚开始的时候,森林里的每一个结点都是一个集合(也就是只有一个结点的树),之后根据题意,逐渐将一个个集合合并(也就是合并成一棵大树)。之后寻找时不断查找父节点,当查找到父结点为本身的结点时,这个结点就是祖宗结点。合并则是寻找这两个结点的祖宗结点,如果这两个结点不相同,则任意将其中一边的集合作为另一边集合的子集。
AC代码:
#include<iostream> using namespace std; int n/*n个元素*/,m/*m个操作*/,f[10001]/*第i个人的祖宗为f[i]*/; int find(int x) //找祖宗(※※重点) { if(f[x]==x) //若自己的祖宗为自己 return f[x]; else return f[x]=find(f[x]);//路径压缩(※※难点):把递归过程中遇到的结点的祖宗结点也直接修改了 } void hebing(int x,int y) //合并操作 { int fx=find(x),fy=find(y); if(fx!=fy) //(其实这一步可有可无,因为之前已经判断过了) f[fx]=fy; //x的祖宗 的父亲 为y的祖宗 return; } int main() { cin>>n>>m; //读入 for(int i=1;i<=n;i++) f[i]=i; //初始化:n个数,每个数祖宗为自己 for(int i=1;i<=m;i++) //依次读入m个操作要求 { int z,x,y; cin>>z>>x>>y; if(z==2) //执行查询操作 { if(find(x)==find(y)) //如果两个人为同一个祖宗,则在一个集合 (※※重点) cout<<"Y"<<endl; else //否则不在一个集合 cout<<"N"<<endl; } else //执行合并操作 hebing(x,y); } return 0; }