提交记录 8409


用户 题目 状态 得分 用时 内存 语言 代码长度
callg noip18d. 【NOIP2018】旅行 Accepted 100 1.48 ms 612 KB C++11 3.30 KB
提交时间 评测时间
2019-02-15 19:58:46 2020-08-01 01:18:22
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
const int M=20005;
int n,m;
int u,v;
int h[N],nx[M],to[M],cnt;
int dfn[N],low[N],idx;
int s[N],t;
bool vis[N];
int loop[N],lcnt;
bool inloop[N],pass[N];
int f[N],scnt,fir,lim,cut;
int mv[N];
bool forbid[M];
inline int get() { int x; cin >> x; return x; }
void addedge(int u,int v)
{
	cnt++;
	to[cnt]=v;
	nx[cnt]=h[u];
	h[u]=cnt;
}
void greedy(int u,int p)
{
	printf("%d ",u);
	int las,cnt,cur;
	las=0;
	cnt=0;
	cur=0;
	for (int i=h[u];i;i=nx[i])
		if (to[i]!=p)
			cnt++;
	for (int i=1;i<=cnt;i++)
	{
		cur=n+1;
		for (int j=h[u];j;j=nx[j])
			if (to[j]!=p)
				if (to[j]>las)
					if (to[j]<cur)
						cur=to[j];
		greedy(cur,u);
		las=cur;
	}
}
void findloop(int u,int las)
{
	idx++;
	dfn[u]=low[u]=idx;
	t++;
	s[t]=u;
	vis[u]=1;
	for (int i=h[u];i;i=nx[i])
		if (i!=(las^1))
			if (!vis[to[i]])
			{
				findloop(to[i],i);
				if (low[to[i]]<low[u])
					low[u]=low[to[i]];
			}
			else
				if (dfn[to[i]]<low[u])
					low[u]=dfn[to[i]];
	if (dfn[u]==low[u])
	{
		if (s[t]==u)
			t--;
		else
		{
			while (s[t]!=u)
			{
				lcnt++;
				loop[lcnt]=s[t];
				t--;
			}
			lcnt++;
			loop[lcnt]=u;
			t--;
		}
	}
}
void flag(int u,int p)
{
	if (u==1)
		pass[u]=1;
	for (int i=h[u];i;i=nx[i])
		if (to[i]!=p&&inloop[to[i]]==0)
		{
			flag(to[i],u);
			pass[u]|=pass[to[i]];
		}
}
void dfs(int u,int p)
{
	printf("%d ",u);
	int las,cnt,cur;
	las=0;
	cnt=0;
	cur=0;
	for (int i=h[u];i;i=nx[i])
		if (to[i]!=p&&forbid[i]==0)
			cnt++;
	for (int i=1;i<=cnt;i++)
	{
		cur=n+1;
		for (int j=h[u];j;j=nx[j])
			if (to[j]!=p&&forbid[j]==0)
				if (to[j]>las)
					if (to[j]<cur)
						cur=to[j];
		dfs(cur,u);
		las=cur;
	}
}
int main()
{
	ios::sync_with_stdio(false); std::cin.tie(0);
	n = get(), m = get();
	cnt++;
	for (int i=1;i<=m;i++)
	{
		u = get(), v = get();
		addedge(u,v);
		addedge(v,u);
	}
	if (n>m)
	{
		greedy(1,0);
		printf("\n");
	}
	else
	{
		findloop(1,0);
		for (int i=1;i<=lcnt;i++)
			inloop[loop[i]]=1;
		flag(loop[lcnt],0);
		for (int i=1;i<=lcnt;i++)
			for (int j=h[loop[i]];j;j=nx[j])
				if (pass[to[j]]==0&&inloop[to[j]]==0)
					if (to[j]>mv[loop[i]])
						mv[loop[i]]=to[j];
		scnt=0;
		for (int i=h[loop[lcnt]];i;i=nx[i])
			if (!pass[to[i]])
			{
				scnt++;
				f[scnt]=to[i];
			}
		sort(f+1,f+scnt+1);
		for (fir=1;fir<=scnt;fir++)
			if (inloop[f[fir]])
				break;
		lim=f[fir+1];
		if (f[fir]==loop[1])
		{
			for (cut=1;cut<lcnt;cut++)
			{
				if (mv[loop[cut]]>loop[cut+1])
				{
					lim=n+1;
					for (int i=h[loop[cut]];i;i=nx[i])
						if (to[i]>loop[cut+1]&&inloop[to[i]]==0)
							if (to[i]<lim)
								lim=to[i];
				}
				if (loop[cut+1]>lim||cut+1==lcnt)
					break;
			}
			for (int i=h[loop[cut]];i;i=nx[i])
				if (to[i]==loop[cut+1])
					forbid[i]=1;
			for (int i=h[loop[cut+1]];i;i=nx[i])
				if (to[i]==loop[cut])
					forbid[i]=1;
		}
		else
		{
			loop[0]=loop[lcnt];
			for (cut=lcnt-1;cut>0;cut--)
			{
				if (mv[loop[cut]]>loop[cut-1])
				{
					lim=n+1;
					for (int i=h[loop[cut]];i;i=nx[i])
						if (to[i]>loop[cut-1]&&inloop[to[i]]==0)
							if (to[i]<lim)
								lim=to[i];
				}
				if (loop[cut-1]>lim||cut-1==0)
					break;
			}
			for (int i=h[loop[cut]];i;i=nx[i])
				if (to[i]==loop[cut-1])
					forbid[i]=1;
			for (int i=h[loop[cut-1]];i;i=nx[i])
				if (to[i]==loop[cut])
					forbid[i]=1;
		}
		dfs(1,0);
		printf("\n");
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #143.33 us76 KBAcceptedScore: 4

Testcase #249.71 us76 KBAcceptedScore: 4

Testcase #350.59 us76 KBAcceptedScore: 4

Testcase #463.25 us80 KBAcceptedScore: 4

Testcase #562.31 us80 KBAcceptedScore: 4

Testcase #6275.8 us156 KBAcceptedScore: 4

Testcase #7275.22 us160 KBAcceptedScore: 4

Testcase #8274.23 us164 KBAcceptedScore: 4

Testcase #9283.5 us140 KBAcceptedScore: 4

Testcase #10285.24 us132 KBAcceptedScore: 4

Testcase #111.327 ms376 KBAcceptedScore: 4

Testcase #121.32 ms440 KBAcceptedScore: 4

Testcase #131.312 ms456 KBAcceptedScore: 4

Testcase #141.324 ms372 KBAcceptedScore: 4

Testcase #151.316 ms504 KBAcceptedScore: 4

Testcase #1646.53 us112 KBAcceptedScore: 4

Testcase #1747.59 us112 KBAcceptedScore: 4

Testcase #1870.43 us116 KBAcceptedScore: 4

Testcase #1970.09 us116 KBAcceptedScore: 4

Testcase #20296.73 us224 KBAcceptedScore: 4

Testcase #21299.22 us224 KBAcceptedScore: 4

Testcase #22298.5 us208 KBAcceptedScore: 4

Testcase #231.466 ms612 KBAcceptedScore: 4

Testcase #241.476 ms588 KBAcceptedScore: 4

Testcase #251.48 ms564 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-31 12:13:13 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用