首页 > 代码库 > [并查集]团伙

[并查集]团伙

2024-10-01 19:05:39   219人阅读

题号：ZHOJ1258

思路：并查集。

给每个人建立一个“正集”（朋友）、一个“反集”（敌人），反集要么为空、要么指向一个正集，维护这两类集合，最后统计“正集”的个数。

 1 #include<cstdio> 2 #include<cstring> 3 const int N=1000; 4 int ans; 5 class UnionFindSet { 6     private: 7         int anc[N],anti[N]; 8     public: 9         UnionFindSet(int n) {10             for(int i=0;i<=n;i++) {11                 anc[i]=i;12                 anti[i]=0;13             }14         }15         int Find(int x) {16             return (x==anc[x])?x:(anc[x]=Find(anc[x]));17         }18         void Union(int op,int x,int y) {19             if(op==1) {20                 if(Find(y)==Find(x)) return;21                 anc[Find(y)]=Find(x);22             }23             if(op==2) {24                 if(anti[x]) Union(1,anti[x],y);25                 if(anti[y]) Union(1,anti[y],x);26                 if(!anti[x]) anti[x]=Find(y);27                 if(!anti[y]) anti[y]=Find(x);28             }29         }30         int Count(int n) {31             bool vis[n+1];32             memset(vis,0,sizeof vis);33             for(int i=1;i<=n;i++) vis[Find(i)]=true;34             int ans=0;35             for(int i=1;i<=n;i++) if(vis[i]) ans++;36             return ans;37         }38 };39 int main() {40     int n,m;41     scanf("%d%d",&n,&m);42     UnionFindSet s(n);43     while(m--) {44         int op,x,y;45         scanf("%d%d%d",&op,&x,&y);46         s.Union(op,x,y);47     }48     printf("%d\n",s.Count(n));49     return 0;50 }

 

[并查集]团伙


联系
我们