首页 > 代码库 > [并查集]团伙
[并查集]团伙
题号: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 }
[并查集]团伙
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。