洛谷 P1892 [BOI2003]团伙（种类并查集）

传送门

解题思路

用并查集f存朋友关系，一个数组e存的是敌人关系，是一个辅助数组，所以叫做种类并查集。

当p和q是朋友时，直接合并，但是当是敌人时，需要一些操作。

当p还没有敌人时（即p的敌人是自己），直接e[p]=q;

否则就把p的敌人和q变成朋友，这也就是变相把p和q变成敌人。

当然，对q也是如此。

最后统计有多少人是祖先，也就是说自己的朋友是自己，统计下来。

AC代码

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int maxn=;

 int f[maxn],e[maxn];

 int n,m;

 char c;

 int find(int x){

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

     return f[x]=find(f[x]);

 }

 int ans;

 int main(){

     cin>>n>>m;

     for(int i=;i<=n;i++) f[i]=i,e[i]=i;

     for(int i=;i<=m;i++){

         int p,q;

         cin>>c>>p>>q;

         if(c=='F'){

             f[find(p)]=find(q);

         }

         else{

             if(e[p]==p)e[p]=find(q);

             else f[find(e[p])]=find(q);

             if(e[q]==q)e[q]=find(p);

             else f[find(e[q])]=find(p);

         }

     }

     for(int i=;i<=n;i++){

         if(f[i]==i) ans++;

     }

     cout<<ans;

     return ;

 }

巴特西

洛谷 P1892 [BOI2003]团伙（种类并查集）

传送门

解题思路

AC代码

最新文章

热门文章