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;

}