Task2004.3 P5543 The Great Revegetation
题目描述：
一场漫长的干旱使农场主约翰的N牧场没有草, 然而, 随着雨季的到来, 是时候“重新种植”了。在农夫约翰的小屋里, 他有两个桶, 分别有一种草籽。他想在他的每一个牧场种草, 在每一个牧场中只能种一种草。 作为一名奶农, 农场主约翰想确保他能满足他的M头奶牛的特殊饮食需求。他每头奶牛都有两个自己最喜欢的牧场。一些奶牛只吃一种草, 因此约翰希望确保在这些奶牛最喜欢的两个牧场里种植同一种的草; 剩下的奶牛则吃不同种类的草。对于那些奶牛，约翰当然想确保它们最喜欢的两块牧场里有不同的草。 请帮助农场主约翰确定他在他的N块牧场上有多少种种植草的不同方式。
思路：
与关押罪犯有很多相似之处，实用并查集补集的思路，将两个牧场种相同草的关系当作「友好」，将两个牧场种不同草的关系当作「敌对」，但值得注意的一点是并非所有的牧场一定为任意一只奶牛所喜爱，所以我们还需要额外的一个并查集来维护被提到的牧场的连通性。
如果产生冲突，那么最终方案数必定为0；若没有冲突，就在第三个并查集中判断连通块，连通块数为为cnt，则$ans=2^{cnt}$;
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,a,b,ans;
char op;
int fa[100005],gr[200005];
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
int com(int x){
if(gr[x]==x) return x;
else return gr[x]=com(gr[x]);
}
int main(){
scanf("%d%d",&n,&m);
ans=n;
for(int i=1;i<=n;i++){
gr[i]=i;
gr[i+n]=i+n;
fa[i]=i;
}
for(int i=1;i<=m;i++){
cin>>op>>a>>b;
// op=getchar();
// getchar();
// scanf("%d%d",&a,&b);
//乖乖用cin（笑）
if(op=='S'){
gr[com(a)]=com(b);
gr[com(a+n)]=com(b+n);
}
else{
if(com(a)==com(b)){
ans=0;
break;
}
gr[com(a+n)]=com(b);
gr[com(a)]=com(b+n);
}
if(find(a)!=find(b)){
fa[find(a)]=find(b);
ans--;
}
}
if(ans==0){
printf("%d",ans);
return 0;
}
printf("1");
for(int i=1;i<=ans;i++) printf("0");
return 0;
}