自动搬运

查看原文

来自洛谷，原作者为

	GUO120822 どうしたの？

搬运于2025-08-24 23:09:47，当前版本为作者最后更新于2025-05-04 15:55:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

图论建模。

令 $id_i$ 表示 $i$ 号运动员在最后一轮的 $id_i$ 号运动员的位置。

倒着建边，初始 $id_i=i$。

每次对于 $id_{x_i}$ 和 $id_{y_i}$ 建边，表示 $id_{x_i}$ 和 $id_{y_i}$ 运动员在最后一轮相邻。

所以建边之后的 $x$ 连接 $y$ 表示 $x$ 与 $y$ 在最后一轮相邻。

然后若有度数大于二的，直接无解。

如果有环，直接无解。

其他情况，找到每个联通块度为一的最小点。

然后直接一一遍历即可。

#include<bits/stdc++.h>
using namespace std;
struct FSI{
	template<typename T>
	FSI& operator >> (T &res){
		res=0;T f=1;char ch=getchar();
		while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
		while (isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
		res*=f;
		return *this;
	}
}scan;
const int N=6e5+10,M=1e6+10;
int n,m,i,x[M],y[M]; 
int last[N],c;
int id[N];
int ans[N],k,d[N];
bool vis[N],v[M];
struct Node{
	int to,next;
}a[M<<1];
struct node{
	int u,v;
}e[M];
void add(int u,int v)
{
	a[++c]={v,last[u]};
	last[u]=c;
}
void dfs(int x)
{
	int i,to;
	vis[x]=true;
	ans[++k]=x;
	for (i=last[x];i;i=a[i].next)
	{
		to=a[i].to;
		if (!vis[to]) dfs(to);
	}
}
bool cmp(node x,node y){return x.u<y.u||(x.u==y.u&&x.v<y.v);}
int main()
{
	scan>>n>>m;
	for (i=1;i<=m;i++) scan>>x[i]>>y[i];
	for (i=1;i<=n;i++) id[i]=i;
	for (i=m;i>=1;i--)
	{
		e[i]={id[x[i]],id[y[i]]};
		if (id[x[i]]>id[y[i]]) swap(e[i].u,e[i].v);
		swap(id[x[i]],id[y[i]]);
	}
	sort(e+1,e+m+1,cmp);
	for (i=1;i<=m;i++)
	{
		if (e[i].u==e[i-1].u&&e[i].v==e[i-1].v) v[i]=true;
	}
	for (i=1;i<=m;i++)
	{
		if (!v[i])
		{
			add(e[i].u,e[i].v);
			add(e[i].v,e[i].u);
			d[e[i].u]++;
			d[e[i].v]++;
		}
	}
	for (i=1;i<=n;i++) if (d[i]>2){puts("No");return 0;}
	for (i=1;i<=n;i++)
	{
		if (!vis[i])
		{
			if (!d[i]) ans[++k]=i,vis[i]=true;
			else if (d[i]==1) dfs(i);
		}
	}
	if (k!=n){puts("No");return 0;}
	puts("Yes");
	for (i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}