记录编号	372541	评测结果	AAAAAAAAAA
题目名称	2443.[HZOI 2016]MC之旅：逃离基友	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.181 s
提交时间	2017-02-18 17:36:19	内存使用	0.63 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define rev(x) ((((x)-1)^1)+1)
using namespace std;
const int maxn=20010;
bool dfs(int);
vector<int>G[maxn];
bool vis[maxn],bad;
int n,m,s[maxn],top,d,x,y;
int main(){
	freopen("T3_.in","r",stdin);
	freopen("T3_.out","w",stdout);
	while(scanf("%d%d",&n,&m)==2){
		n<<=1;
		for(int i=0;i<=n;i++)G[i].clear();
		fill(vis,vis+n+1,false);
		bad=false;
		while(m--){
			scanf("%d%d",&d,&x);
			if(d>2)scanf("%d",&y);
			if(d==1)G[rev(x)].push_back(x);
			else if(d==2)G[x].push_back(rev(x));
			else if(d==3){
				G[rev(x)].push_back(x);
				G[rev(y)].push_back(y);
			}
			else if(d==4){
				G[rev(x)].push_back(x);
				G[y].push_back(rev(y));
			}
			else if(d==5){
				G[rev(x)].push_back(y);
				G[rev(y)].push_back(x);
			}
			else if(d==6){
				G[rev(x)].push_back(rev(y));
				G[y].push_back(x);
			}
			else if(d==7||d==12){
				G[x].push_back(rev(y));
				G[y].push_back(rev(x));
			}
			else if(d==8){
				G[x].push_back(rev(x));
				G[y].push_back(rev(y));
			}
			else if(d==9){
				G[x].push_back(rev(y));
				G[rev(x)].push_back(y);
				G[y].push_back(rev(x));
				G[rev(y)].push_back(x);
			}
			else{
				G[x].push_back(y);
				G[rev(x)].push_back(rev(y));
				G[y].push_back(x);
				G[rev(y)].push_back(rev(x));
			}
		}
		for(int i=1;i<=n;i+=2)if(!vis[i]&&!vis[rev(i)]){
			top=0;
			if(!dfs(i)){
				while(top)vis[s[top--]]=false;
				if(!dfs(i+1)){
					bad=true;
					break;
				}
			}
		}
		if(bad)printf("die");
		else for(int i=1;i<=n;i++)if(vis[i])printf("%d ",i);
		printf("\n");
	}
	return 0;
}
bool dfs(int x){
	if(vis[rev(x)])return false;
	if(vis[x])return true;
	vis[x]=true;
	s[++top]=x;
	for(int i=0;i<(int)G[x].size();i++)if(!dfs(G[x][i]))return false;
	return true;
}