P1892 [BOI2003]团伙
斯德哥尔摩
2018-08-01 23:21:49
[P1892 [BOI2003]团伙](https://www.luogu.org/problemnew/show/P1892)
说实话，好久没有做过这么水的题了。。。
表示$NOI$有一题很像：[P2024 [NOI2001]食物链](https://www.luogu.org/problemnew/show/P2024)
然后就~~莫名其妙~~熟练地拆点：
$x$表示$x$的朋友（这个容易吧。。。）
$x+n$表示$x$的敌人（这个也不难）
如果$x$与$y$是朋友，合并$x$和$y$。
否则合并$x+n$和$y$，$y+n$和$x$（$x$的敌人是$y$，$y$的敌人是$x$）。
注意合并的顺序。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 2010
using namespace std;
int n,m,fa[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void uniun(int x,int y){x=find(x);y=find(y);if(x!=y)fa[y]=x;}
void work(){
int ans=0;
for(int i=1;i<=n;i++)if(find(i)==i)ans++;
printf("%d\n",ans);
}
void init(){
char ch[2];
int x,y;
n=read();m=read();
for(int i=1;i<=(n<<1);i++)fa[i]=i;
for(int i=1;i<=m;i++){
scanf("%s",ch);x=read();y=read();
if(ch[0]=='F')uniun(x,y);
else{uniun(x,y+n);uniun(y,x+n);}
}
}
int main(){
init();
work();
return 0;
}
```