记录编号	100613	评测结果	AAAAAAAAAAAAAA
题目名称	[POI 2001] 和平委员会	最终得分	100
用户昵称	FF_Sky||幻	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2014-05-06 20:31:31	内存使用	1.81 MiB

#include <cstdio>
using namespace std;

const int N = 16500;
const int M = 41000;

int ver[M],ver2[M],tot,tot2,next[M],next2[M],ff[M],head[N],head2[N],dnf[N],low[N],num,sum,p,s[N],chu[N],n,nn,c[N],ret,q[M],opp[N],vv[N];
bool v[N];
char ch;

int min(int x,int y){
	return x < y? x : y;
}

int read()
{
	ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	ret = ch-48;
	ch = getchar();
	while (ch >= '0' && ch <= '9')
	{
		(ret *= 10) += ch-48;
		ch = getchar();
	}
	return ret;
}

void add(int x,int y){
	ver[++tot] = y;
	ff[tot] = x;
	next[tot] = head[x];
	head[x] = tot;
}

void add2(int x,int y){
	ver2[++tot2] = y;
	next2[tot2] = head2[x];
	head2[x] = tot2;
}

void tarjan(int x){
	dnf[x] = low[x] = ++num;
	s[++p] = x; v[x] = 1;
	for (int j = head[x]; j; j = next[j]){
		if (!dnf[ver[j]]){
			tarjan(ver[j]);
			low[x] = min(low[x],low[ver[j]]);
		}
		else
			if (v[ver[j]]) low[x] = min(low[x],dnf[ver[j]]);
	}
	if (dnf[x] == low[x]){
		int y;
		sum++;
		do{
			y = s[p--];
			v[y] = 0;
			c[y] = sum;
		}while (y != x);
	}
}
void bfs(){
	int l,r,i,j,x;
	l = 1; r = 0;
	for (i = 1; i <= sum; i++){
		if (chu[i] == 0) q[++r] = i;
	}
	while (l <= r){
		x = q[l]; l++;
		if (vv[x]) continue;
		vv[x] = 1; vv[opp[x]] = 2;
		for (j = head2[x]; j; j = next2[j]){
			if (!(--chu[ver2[j]])){
				q[++r] = ver2[j];
			}
		}
	}
}

int main(){
	freopen("spo.in","r",stdin);
	freopen("spo.out","w",stdout);
	int m,x,y,i;
	n = read(); m = read();
	for (i = 0; i < m; i++){
		x = read()-1; y = read()-1;
		if (x != (y^1)){
			add(x,y^1);
			add(y,x^1);
		}
	}
	nn = n<<1;
	for (i = 0; i < nn; i++)
		if (!dnf[i]) tarjan(i);
	for (i = 0; i < n; i++){
		if (c[i<<1] == c[(i<<1)+1]){
			printf("NIE\n");
			return 0;
		}
		opp[c[i<<1]] = c[(i<<1)+1];
		opp[c[(i<<1)+1]] = c[i<<1];
	}
	for (i = 1; i <= tot; i++){
		if (c[ver[i]] != c[ff[i]]){
			add2(c[ver[i]],c[ff[i]]);
			chu[c[ff[i]]]++;
		}
	}
	bfs();
	for (i = 0; i <= nn; i++)
		if (vv[c[i]] == 1) printf("%d\n",i+1);
	return 0;
}