zcmimi's blog

查看原题

点击跳转

#include<bits/stdc++.h>
const int N=16011;
int n,m,cnt,head[N];
struct edge{int to,nxt;}e[400011];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
int dfn[N],low[N],sz,st[N],tp,bl[N],tt;
bool v[N];
void cmin(int&x,int y){if(y<x)x=y;}
void tarjan(int x){
    dfn[x]=low[x]=++sz;st[++tp]=x;v[x]=1;
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(!dfn[to])tarjan(to),cmin(low[x],low[to]);
        else if(v[to])cmin(low[x],dfn[to]);
    if(low[x]==dfn[x]){
        ++tt;
        while(int k=st[tp--]){
            bl[k]=tt;v[k]=0;
            if(k==x)break;
        }
    }
}
#define p(x) (x&1)?x+1:x-1
#define l(x) x*2-1
#define r(x) x*2
int main(){
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;++i)
        scanf("%d%d",&x,&y),
        add(x,p(y)),add(y,p(x));
    for(int i=1;i<=n*2;++i)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;++i)if(bl[l(i)]==bl[r(i)])return puts("NIE"),0;
    for(int i=1;i<=n;++i)printf("%d\n",bl[l(i)]<bl[r(i)]?l(i):r(i));
}
LG 5782 [POI2001]和平委员会
comment评论
Search
search