提交记录 7003


用户 题目 状态 得分 用时 内存 语言 代码长度
Snakes noip18d. 【NOIP2018】旅行 Accepted 100 1.223 ms 560 KB C++ 3.22 KB
提交时间 评测时间
2018-12-08 16:50:37 2020-08-01 00:56:58


#include <cstdio>
#include <algorithm>
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];
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()
{
	scanf("%d%d",&n,&m);
	cnt++;
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		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 #111.46 us32 KBAcceptedScore: 4

Testcase #214.94 us32 KBAcceptedScore: 4

Testcase #315.72 us32 KBAcceptedScore: 4

Testcase #430.29 us36 KBAcceptedScore: 4

Testcase #529.11 us36 KBAcceptedScore: 4

Testcase #6203.62 us108 KBAcceptedScore: 4

Testcase #7203.15 us112 KBAcceptedScore: 4

Testcase #8201.96 us116 KBAcceptedScore: 4

Testcase #9211.75 us92 KBAcceptedScore: 4

Testcase #10211.69 us84 KBAcceptedScore: 4

Testcase #111.068 ms328 KBAcceptedScore: 4

Testcase #121.062 ms392 KBAcceptedScore: 4

Testcase #131.051 ms408 KBAcceptedScore: 4

Testcase #141.065 ms324 KBAcceptedScore: 4

Testcase #151.061 ms456 KBAcceptedScore: 4

Testcase #1616.55 us68 KBAcceptedScore: 4

Testcase #1716.51 us68 KBAcceptedScore: 4

Testcase #1837.12 us72 KBAcceptedScore: 4

Testcase #1936.9 us72 KBAcceptedScore: 4

Testcase #20229.91 us176 KBAcceptedScore: 4

Testcase #21230.03 us176 KBAcceptedScore: 4

Testcase #22230.39 us160 KBAcceptedScore: 4

Testcase #231.216 ms560 KBAcceptedScore: 4

Testcase #241.218 ms532 KBAcceptedScore: 4

Testcase #251.223 ms508 KBAcceptedScore: 4


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