题目描述

blablabla

样例

//1519 1519：和平委员会 ,计算每个党派的代表i（奇数+1，偶数-1），建立边的仇恨关系，跑一下 tarjan，
// 判断相邻2个党派 i 与i+1，是不是在一个圈子里面，在的话，完蛋了，不在的话，输出每个圈子的编号
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>

using namespace std;
typedef long long LL;
const int N=2e4+5,M=4e5+5;
int head[N],idx,hs[N];;
int to[M*2],ne[M*2]; //又重新 建立了hs的边 ，需要增加一倍
int w[N];//点权
int dfn[N],low[N],dfncnt=0;
int in_stack[N],st[N],top;
int col[N],scc_cnt=0;//染色
int n,m;

void addedge(int h[],int u,int v)
{
    to[idx]=v,ne[idx]=h[u],h[u]=idx++;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++dfncnt;
    in_stack[u]=1,st[++top]=u;
    for(int i=head[u];i!=-1;i=ne[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stack[v]==1)// 访问过，但是在栈里面
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    //退栈，找到总根
    if(dfn[u]==low[u])
    {
        ++scc_cnt;

        while(1)
        {
            int v=st[top--];
            in_stack[v]=0;
            col[v]=scc_cnt;
            if(v==u)
            break;
        }
    }

}
// 计算x的序号，奇数 x+1,偶数 x-1
int calc(int x)
{
    if(x&1)
    return x+1;
    else
    return x-1;
}
int main()
{
    cin>>n>>m;
    memset(head,-1,sizeof head);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        addedge(head,x,calc(y));
        addedge(head,y,calc(x));
    }
    // 1-2n 跑一下tarjan
    for(int i=1;i<=2*n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    //计算 相邻2个数是否相互仇恨
    for(int i=1;i<=2*n;i+=2)
    {
        if(col[i]==col[i+1])
        {
            cout<<"NIE";
            return 0;
        }
    }
    // 
    for(int i=1;i<=2*n;i+=2)
    {
        if(col[i]<col[i+1])
        {
            printf("%d\n",i);
        }
        else
        printf("%d\n",i+1);
    }
    return 0;

}