D36 2-SAT P5782 [POI2001] 和平委员会

#include<bits/stdc++.h>
using namespace std;
const int N=1.6e4+10;
vector<int>G[N];
int tsp,cnt,dfn[N],low[N],scc[N];
stack<int> stk;bool instk[N];
void tarjan(int x)
{
    dfn[x]=low[x]=++tsp;
    stk.push(x);instk[x]=1;
    for(int y:G[x])
	{
        if(!dfn[y])
		{
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
	{
        cnt++;
        for(int z=-1;z!=x;)
        {
            z=stk.top();stk.pop();instk[z]=0;
            scc[z]=cnt;
        }
    }
}
int other(int x){ return((x%2)?x+1:x-1);}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    
    for(int i=1,x,y;i<=m;i++)
	{
        scanf("%d%d",&x,&y);
        G[x].push_back(other(y));
        G[y].push_back(other(x));
    }
    
    tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));
    for(int i=1;i<=2*n;i++)if(!dfn[i]) tarjan(i);
    
    for(int i=1;i<=2*n;i+=2)
        if(scc[i]==scc[i+1])
        {
            puts("NIE");
            return 0;
        }
    for(int i=1;i<=2*n;i+=2)
        if(scc[i]<scc[i+1]) printf("%d\n",i);
        else printf("%d\n",i+1);
    return 0;
}