自动搬运

查看原文

来自洛谷，原作者为

	Su_Zipei 与卿再世相逢日,玉树临风一少年

搬运于2025-08-24 22:25:39，当前版本为作者最后更新于2020-11-04 11:34:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先发现这题要求的是哈密顿回路，然后一看是NPC问题瞬间劝退。。其实是有特点的，对于这道题来说，特点就是合法的图中出度大于2的点不会很多，最多只有$20$个，而对于出度为$1$的点是没必要去跑的，因为知道走上去之后的结果，所以事实上只需要对这二十个点跑一下就行，那么可以把所有的链都缩起来，这样时间复杂度的极限也才$20*2^{20}$，可以通过。

#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
struct Edge{
	int to,nxt;
}e[N<<1];
int n,m;
int h[N],idx,nxt[N],d[N];
void Ins(int a,int b){
	e[++idx].to=b;e[idx].nxt=h[a];h[a]=idx;
}
vector<int> vec;
bool vis[N],inq[N];
bool check(){
	memset(inq,0,sizeof(inq));
	for(int i=1,now=1;i<=n;i++,now=nxt[now]){
		if(inq[now])return 0;
		inq[now]=1;
	}
	return 1;
}
void dfs(int u){
	if(u==vec.size()){
		if(check()){
			for(int i=1,now=1;i<=n;i++,now=nxt[now])
				printf("%d ",now);
			printf("1 ");
			exit(0);
		}
		return;
	}
	int now=vec[u];
	for(int i=h[now];i;i=e[i].nxt){
		int v=e[i].to;
		if(vis[v])continue;
		vis[v]=1;
		nxt[now]=v;
		dfs(u+1);
		vis[v]=0;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		Ins(a,b);d[a]++;
	}
	for(int i=1;i<=n;i++){
		if(d[i]>=2)vec.push_back(i);
		else if(d[i]==0)return puts("There is no route, Karl!"),0;
		else {
			int v=e[h[i]].to;
			if(vis[v])return puts("There is no route, Karl!"),0;
			vis[v]=1;
			nxt[i]=v;
		}
	}
	dfs(0);
	return puts("There is no route, Karl!"),0;
}