题目链接：P5543 [USACO19FEB]The Great Revegetation S
好坑啊，都身败名裂了。

思路一：

考虑染色法，跑一遍搜所就好了，不给代码了。

思路二：

考虑并查集，我想到一个\(O(n\alpha(n)+n\log n)\)的做法，首先维护多少不能联系的集合，根据简单的排列组合知识就知道是\(2^n(n\text{是集合数})\)。
再开一个来判断是否矛盾就好了，这里用了一个并查集，中间清空一下就好了。
思考：何时不合法？(搜索也要注意呀)
显然要判断S与D的排斥，还有D与D的排斥，为了不枚举，排一下序，记得开两倍存储空间。（所以呢，\(92\)卡了好久）

\(Code\):

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100005;
int f[MAXN],n,m,ans=0;
void init(){for(int i=0;i<=n+1;i++) f[i]=i;}
int getf(int u){return f[u]=(f[u]==u?u:getf(f[u]));}
void merge(int u,int v)
{
    int t1=getf(u),t2=getf(v);
    if(t1!=t2) f[t2]=t1;
    return;
}
char flag;
int u,v,id[MAXN]={0};
struct node1
{
    int x,y;
}a[MAXN];
struct node2
{
    int x,y;
}b[MAXN<<1];
bool cmp(node2 n,node2 m){return n.x<m.x;}
int c=0,cnt=0;
int main()
{
    //freopen("data.in","r",stdin);
    //freopen("baoli.out","w",stdout);
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=m;i++)
    {
        cin>>flag>>u>>v;
        if(flag=='S') c++,a[c].x=u,a[c].y=v;
        else if(flag=='D') 
        {
            cnt++,b[cnt].x=u,b[cnt].y=v;
            cnt++,b[cnt].x=v,b[cnt].y=u; 
        } 
        merge(u,v);
    }
    for(int i=1;i<=n;i++) if(f[i]==i) ans++;
    sort(b+1,b+cnt+1,cmp);
    int now=0;
    init();
    for(int i=1;i<=cnt;i++)
    {
        if(b[i].x==b[now].x) merge(b[i].y,b[now].y);
        else now=i; 
    }
    for(int i=1;i<=c;i++) merge(a[i].x,a[i].y);
    for(int i=1;i<=cnt;i++) if(getf(b[i].x)==getf(b[i].y)){printf("0\n");return 0;}
    printf("1");
    for(int i=1;i<=ans;i++) printf("0");
    printf("\n");
    return 0;
}