学步园

论文题目链接：Click here~~

复杂度O(E)。

#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 16005;
const int M = 40005;

struct Vertex
{
    int head;
}V[N],VV[N];

struct Edge
{
    int v,next;
}E[M],EE[M];

int top,topp,scc,id,dfn[N],low[N],ind[N],belong[N],opp[N];

bool in[N],vis[N],color[N];

stack<int> S;

void init()
{
    top = topp = 0;
    memset(V,-1,sizeof(V));
    memset(VV,-1,sizeof(VV));
}

void add_edge(int u,int v)
{
    E[top].v = v;
    E[top].next = V[u].head;
    V[u].head = top++;
}

void add_edge2(int u,int v)
{
    EE[topp].v = v;
    EE[topp].next = VV[u].head;
    VV[u].head = topp++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++id;
    S.push(u);
    in[u] = true;
    for(int i=V[u].head;~i;i=E[i].next)
    {
        int v = E[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        int v;
        do
        {
            v = S.top();
            S.pop();
            in[v] = false;
            belong[v] = scc;
        }while(u != v);
        scc++;
    }
}

void get_scc(int n)
{
    scc = id = 0;
    memset(dfn,0,sizeof(dfn));
    memset(in,false,sizeof(in));
    for(int i=0;i<n;i++)
        if(!dfn[i])
            tarjan(i);
}

bool conflict(int n)
{
    for(int i=0;i<n;i++)
        if(belong[i<<1] == belong[i<<1|1])
            return true;
        else
        {
            opp[ belong[i<<1] ] = belong[i<<1|1];
            opp[ belong[i<<1|1] ] = belong[i<<1];
        }
    return false;
}

void rebuild(int n)
{
    memset(ind,0,sizeof(ind));
    for(int u=0;u<n;u++)
    {
        for(int j=V[u].head;~j;j=E[j].next)
        {
            int v = E[j].v;
            if(belong[u] == belong[v])
                continue;
            ind[belong[u]]++;                   //ni'tu
            add_edge2(belong[v],belong[u]);
        }
    }
}

void topSort()
{
    memset(vis,false,sizeof(vis));
    memset(color,false,sizeof(color));
    queue<int> q;
    for(int i=0;i<scc;i++)
        if(!ind[i])
            q.push(i);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        if(vis[u])
            continue;
        vis[u] = true;
        color[u] = true;
        int v = opp[u];
        if(!vis[v])
            vis[v] = true;
        for(int i=VV[u].head;~i;i=EE[i].next)
        {
            int v = EE[i].v;
            if(--ind[v] == 0)
                q.push(v);
        }
    }
}

int main()
{
    //freopen("in.ads","r",stdin);
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        while(m--)
        {
            int u,v;
            char c1,c2;
            scanf("%d %d",&u,&v);
            --u , --v;
            add_edge(u,v^1);
            add_edge(v,u^1);
        }
        get_scc(n<<1);
        if(conflict(n))
            puts("NIE");
        else
        {
            rebuild(n<<1);
            topSort();
            for(int i=0;i<n;i++)
                printf("%d\n",color[ belong[i<<1] ] ? i<<1|1 : i+1<<1);
        }
    }
    return 0;
}