记录编号	192680	评测结果	A
题目名称	[CEPC2001]爱丽丝和鲍勃	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.074 s
提交时间	2015-10-12 14:28:59	内存使用	11.89 MiB

#include<cstdio>
#include<deque>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEN=10010,maxn=0x7fffffff;
int d;
int N,M,f[SIZEN]={0},w[SIZEN]={0},dfn[SIZEN]={0},low[SIZEN]={0},son[SIZEN]={0},tot=0;
deque<int> s[SIZEN],c[SIZEN];
int ans[SIZEN]={0};
bool visit[SIZEN]={0};
void add(int fr,int to)
{
	c[fr].push_back(to);
	c[to].push_back(fr);
}
bool check(int x,int v)
{
	for(int i=0;i<s[v].size();i++) 
	{
		int w=s[v][i];
		if(f[w]==v)
		{
			if(low[w]<dfn[x]) return 1;
			return 0;
		}
	}
}
void dfs(int x)
{
	//cout<<x<<endl;
	dfn[x]=++tot;
	low[x]=dfn[x];
	w[x]=x;
	for(int i=0;i<s[x].size();i++)
	{
		int v=s[x][i];
		if(f[x]==v) continue;
		if(f[v]==0&&v!=1)
		{
			son[x]++;
			f[v]=x;
			dfs(v);
			low[x]=min(low[x],low[v]);
			if(son[v]==0) 
			{
				add(x,v);add(v,w[v]);
				//if((x==1&&v==6)||(x==6&&v==1)) cout<<"error"<<endl;
		    }
			if(son[v]==1)
		    {
				if(x==1) add(x,v);
			    else if(check(x,v)) add(x,v);
				else add(w[v],v);
				//if((x==1&&v==6)||(x==6&&v==1)) cout<<"error"<<endl;
		    }
		}
		else
		{
			if(dfn[v]<low[x])
			{
			low[x]=dfn[v];
			w[x]=v;
			}
		}
	}
}
void read()
{
	scanf("%d%d",&N,&M);
	//cout<<N<<endl;
	for(int i=1;i<=N;i++) s[i].clear(),c[i].clear();
	for(int i=1;i<=(N+M);i++)
	{
		int fr,to;
		scanf("%d%d",&fr,&to);
		s[fr].push_back(to);
		s[to].push_back(fr);
	}
}
void dfs2(int x,int fa)
{
	int now=maxn;
	ans[++tot]=x;
	visit[x]=1;
	for(int i=0;i<c[x].size();i++) if(c[x][i]!=fa&&visit[c[x][i]]==0&&c[x][i]<now) now=c[x][i];
	if(now!=maxn) dfs2(now,x);
}
void check_c()
{
	for(int i=1;i<=N;i++)
	{
		cout<<"i:"<<i<<endl;
		for(int j=0;j<c[i].size();j++)
		{
			cout<<c[i][j]<<" ";
		}
		cout<<endl;
	}
}
int main()
{
	freopen("aliceandbob.in","r",stdin);
	freopen("aliceandbob.out","w",stdout);
	scanf("%d",&d);
	while(d)
	{
		d--;
		read();
		tot=0;
		memset(son,0,sizeof(son));memset(dfn,0,sizeof(dfn));memset(w,0,sizeof(w));memset(f,0,sizeof(f));
		memset(low,0,sizeof(low));
		dfs(1);
		ans[1]=1;tot=0;
		//check_c();
		//for(int i=1;i<=N;i++) cout<<dfn[i]<<" ";
		//cout<<endl;
		memset(visit,0,sizeof(visit));memset(ans,0,sizeof(ans));
		dfs2(1,0);
		for(int i=1;i<=N;i++) printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}