题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1370
把一个点拆成两个点，i–>i，i+n
如果两个人是朋友，合并(x,y)
如果是敌人，合并(x,y+n) (y,x+n)
如果一个连通块有一个点在1~n内，那么它会使ans++
所以最后数一下1~n（注意不是到n*2）里有多少个不同的连通块
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<bits/stdc++.h> #define MAXN 1010 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int n,m,fa[MAXN*2],ans; bool vis[MAXN*2]; int getroot(int x){ if(fa[x]==x)return x; return fa[x]=getroot(fa[x]); } inline void un(int x,int y){ x=getroot(x); y=getroot(y); fa[x]=y; } int main(){ n=rd(),m=rd(); for(int i=1; i<=2*n; i++)fa[i]=i; while(m--){ char op[2]; scanf("%s",op); int x=rd(),y=rd(); if(op[0]=='E')un(x,y+n),un(y,x+n); if(op[0]=='F')un(x,y); } for(int i=1; i<=n; i++){ int x=getroot(i); if(!vis[x])vis[x]=1,ans++; } printf("%d\n",ans); return 0; } |
