1823: [JSOI2010]满汉全席 2-sat

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=1823

思路

建图，缩点tarjan
判断impossible

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m;
struct node {
    int v,nxt;
}e[N<<1];
int head[N<<1],mmp;
void add(int u,int v) {
    e[++mmp].v=v;
    e[mmp].nxt=head[u];
    head[u]=mmp;
}
int stak[N],top,cnt,vis[N],dfn[N],low[N],belong[N];
void tarjan(int u) {
    dfn[u]=low[u]=++cnt;
    stak[++top]=u;
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        } else if(vis[v]) {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]) {
        belong[0]++;
        while(stak[top]!=u) {
            vis[stak[top]]=0;
            belong[stak[top]]=belong[0];
            top--;
        } top--;
        vis[u]=0;
        belong[u]=belong[0];
    }
}
void solve() {
    memset(head,0,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    belong[0]=top=cnt=0;
    n=read(),m=read();
    for(int k=1;k<=m;++k) {
        char a=getchar();
        while(a!='m'&&a!='h') a=getchar();
        int i=read();
        char b=getchar();
        while(b!='m'&&b!='h') b=getchar();
        int j=read();
        int x= a=='m' ? 1 : 0,y= b=='m' ? 1 : 0;
        add(i+n*x,j+n*(y^1));
        add(j+n*y,i+n*(x^1));
    }
    for(int i=1;i<=2*n;++i)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;++i) {
        if(belong[i]==belong[i+n]) {
            puts("BAD");
            return;
        }
    }
    puts("GOOD");
}
int main() {
    int T=read();
    while(T--) {
        solve();
    }
    return 0;
}