题目大意
给你一张图，求这张图的汉密尔顿回路。
分析
因为m≤n+20，所以如果存在回路一定是在一个环中加入了至多20条边。我们先考虑dfs，但我们发现如果出现图1这种情况就会是复杂度爆炸
图1
图2
我们发现如果有很多这样的三角形程序就会爆炸。所以我们考虑优化。我们发现对于所有出度为1的点我们完全不必枚举它的出边，所以根据这些就写出了代码1，然后它居然能水过，但是对于像图2这种数据它就只有被卡掉的份啦，所以我们考虑继续优化。我们考虑将所有只有一条路径的点从图中真实的去掉，也就是说我们将所有点的相连关系提前记录下来，以便后续输出答案，而在搜索过程中只考虑出度不为1的点，听起来可能有些麻烦，参照代码2看看写写就好理解了。
代码1
#include<bits/stdc++.h>
using namespace std;
vector<int>v[100050];
int n,m,x[100050],y[100050],vis[100050],id[100050],od[100050],nxt[100050];
int ans[100050];
inline void bad(){
puts("There is no route, Karl!");
exit(0);
}
inline void dfs(int x){
if(vis[x])return;
vis[x]=1;
for(int i=0;i<v[x].size();i++)dfs(v[x][i]);
}
inline void pr(){
for(int i=0;i<=n;i++)
printf(" %d",ans[i]);
puts("");
exit(0);
}
inline void search(int x,int cnt){
if(cnt==n){
ans[cnt]=x;
if(x==1)pr();
return;
}
if(vis[x])return;
ans[cnt]=x;
vis[x]=1;
if(nxt[x]){
search(nxt[x],cnt+1);
}else {
for(int i=0;i<v[x].size();i++){
search(v[x][i],cnt+1);
}
}
vis[x]=0;
return;
}
int main(){
freopen("king.in","r",stdin);
freopen("king.out","w",stdout);
scanf("%d%d",&n,&m);
if(m<n)bad();
for(int i=1;i<=m;++i){
scanf("%d%d",&x[i],&y[i]);
v[x[i]].push_back(y[i]);
}
memset(vis,0,sizeof(vis));
dfs(1);
for(int i=1;i<=n;i++)
if(!vis[i])
bad();
for(int i=1;i<=n;i++)v[i].clear();
for(int i=1;i<=m;i++){
v[y[i]].push_back(x[i]);
}
memset(vis,0,sizeof(vis));
dfs(1);
for(int i=1;i<=n;i++)
if(!vis[i])
bad();
for(int i=1;i<=n;i++)v[i].clear();
for(int i=1;i<=m;i++){
v[x[i]].push_back(y[i]);
if(od[x[i]]==0)od[x[i]]=y[i];
else if(od[x[i]]!=y[i])od[x[i]]=-1;
if(id[y[i]]==0)id[y[i]]=x[i];
else if(id[y[i]]!=x[i])id[y[i]]=-1;
}
for(int i=1;i<=n;i++)
if(od[i]==0||id[i]==0)
bad();
for(int i=1;i<=n;i++)
if(od[i]>0&&id[i]>0){
nxt[i]=od[i];
nxt[id[i]]=i;
}
memset(vis,0,sizeof(vis));
search(1,0);
bad();
return 0;
}
代码2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define sp cout<<"---------------------------------------------------"<<endl
vector<int>v[110000];
vector<int>cpx;
int nxt[110000],vis[110000],arr[110000],n,m;
inline void bad(){
puts("There is no route, Karl!");
exit(0);
}
inline void check(){
int i,x;
memset(arr,0,sizeof(arr));
for(i=1,x=1;i<=n;i++,x=nxt[x]){
if(arr[x])return;
arr[x]=1;
}
for(i=1,x=1;i<=n;i++,x=nxt[x]){
printf("%d ",x);
}
cout<<1<<endl;
exit(0);
}
inline void work(int wh){
if(wh==cpx.size()){
check();
return;
}
int x=cpx[wh];
for(int i=0;i<v[x].size();i++)
if(!vis[v[x][i]]){
nxt[x]=v[x][i];
vis[v[x][i]]=1;
work(wh+1);
vis[v[x][i]]=0;
}
return;
}
int main(){
freopen("king.in","r",stdin);
freopen("king.out","w",stdout);
int i,j,k;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
}
for(i=1;i<=n;i++)
if(v[i].empty())bad();
for(i=1;i<=n;i++)
if(v[i].size()>1){
cpx.push_back(i);
}else {
if(vis[v[i][0]])bad();
vis[v[i][0]]=1;
}
for(i=1;i<=n;i++)
nxt[i]=v[i][0];
work(0);
bad();
return 0;
}