HIT 1917 2—SAT

题目大意：一国有n个党派，每个党派在议会中都有2个代表，

现要组建和平委员会，要从每个党派在议会的代表中选出1人，一共n人组成和平委员会。

已知有一些代表之间存在仇恨，也就是说他们不能同时被选为和平委员会的成员，

现要你判断满足要求的和平委员会能否创立？如果能，请任意给出一种方案。（ POI 0106 ）

—————————————————————————————————————————

这道题就是裸的2—SAT

不过我用了tarjan缩点 然后一波拓排

tips：一个问题无解当且仅当一个集合的两个点在同一个联通块里面

所以特判完无解之后一波拓排就可以解决问题辣

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using std::min;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m;

int next(int x){return x&?x+:x-;}

struct node{int from,to,next;}e[*M],q[*M];

int first[M],cnt;

void ins(int a,int b){e[++cnt]=(node){a,b,first[a]}; first[a]=cnt;}

int star[M],sum;

void insq(int a,int b){q[++sum]=(node){a,b,star[a]}; star[a]=sum;}

int dfn[M],low[M],st[M],last[M],top,tot;

int color[M],h,in[M],op[M],ans[M];

void tarjan(int x){

    dfn[x]=low[x]=++tot; st[++top]=x; last[x]=top;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(!dfn[now]) tarjan(now),low[x]=min(low[x],low[now]);

        else if(!color[now]) low[x]=min(low[x],dfn[now]);

    }

    if(dfn[x]==low[x]) for(h++;top>=last[x];top--) color[st[top]]=h;

}

bool f;

void topsort(){

    std::queue<int>qu;

    for(int i=;i<=h;i++)if(!in[i]) qu.push(i);

    while(!qu.empty()){

        int x=qu.front(); qu.pop();

        if(!ans[x]) ans[x]=,ans[op[x]]=-;

        for(int i=star[x];i;i=q[i].next){

            int now=q[i].to; in[now]--;

            if(!in[now]) qu.push(now);

        }

    }

}

void clear(){

    f=false;

    cnt=sum=h=tot=;

    memset(color,,sizeof(color));

    memset(last,,sizeof(last));

    memset(dfn,,sizeof(dfn));

    memset(st,,sizeof(st));

    memset(low,,sizeof(low));

    memset(in,,sizeof(in));

    memset(first,,sizeof(first));

    memset(star,,sizeof(star));

    memset(op,,sizeof(op));

    memset(ans,,sizeof(ans));

}

int main(){

    int x,y;

    while(scanf("%d %d",&n,&m)==){

        clear();

        for(int i=;i<=m;i++) x=read(),y=read(),ins(x,next(y)),ins(y,next(x));

        for(int i=;i<=*n;i++) if(!dfn[i]) tarjan(i);

        for(int i=;i<=n;i++)if(color[i<<]==color[next(i<<)]){printf("NIE\n"); f=true; break;}

        else op[color[i<<]]=color[next(i<<)],op[color[next(i<<)]]=color[i<<];

        if(f) continue;

        for(int i=;i<=cnt;i++)if(color[e[i].from]!=color[e[i].to]) insq(color[e[i].to],color[e[i].from]),in[color[e[i].from]]++;

        topsort();

        for(int i=;i<=n;i++)

            if(ans[color[i<<]]==) printf("%d\n",i<<);

            else printf("%d\n",next(i<<));

    }

    return ;

}