自动搬运

查看原文

来自洛谷，原作者为

	potatoler 这个人逊死了，什么也没能留下

搬运于2025-08-24 22:11:51，当前版本为作者最后更新于2020-02-04 22:44:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述：

一场漫长的干旱使农场主约翰的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;
}