BeMissJRsdog @ 2022-09-06 19:45:26
#include<bits/stdc++.h>
using namespace std;
int st=1,en=1,m,n,b[10001];
bool flag;
int rd[501];
int sum[501][501],mp[501][501],used[501][501];
inline void dfs(register int k,register int u){
if(flag)return;
// printf("%d\n",u);
if(k==m+1){
for(register int i=1;i<k;i++)printf("%d\n",b[i]);
printf("%d",u);
flag=1;
return;
}
for(register int i=1;i<=n;i++){
if(flag)return;
if(used[u][i]>=sum[u][i])continue;
if(!mp[u][i])continue;
used[u][i]++;
used[i][u]++;
b[k]=u;
dfs(k+1,i);
used[u][i]--;
used[i][u]--;
}
}
int main(){
scanf("%d",&m);
// if(m==500){
//
// }
for(register int i=1;i<=m;i++){
register int u,v;
scanf("%d%d",&u,&v);
n=max(n,max(u,v));
// printf("%d %d\n",u,v);
mp[u][v]=mp[v][u]=1;
sum[u][v]++;
sum[v][u]++;
rd[u]++;
rd[v]++;
}
// for(register int i=1;i<=n;i++){
// for(register int j=1;j<=n;j++){
// cout<<mp[i][j]<<' ';
// }
// cout<<'\n';
// }
register int sum=0;
for(register int i=1;i<=n;i++){
if(rd[i]%2!=0){
sum++;
if(sum==1){
st=i;
}
if(sum==2){
en=i;
}
}
}
dfs(1,min(st,en));
return 0;
}
https://wwz.lanzouy.com/iHKWv0b6iffg
by wenjingqi @ 2022-11-20 14:29:06
深搜要等找到正确路线再存储 比如数据
4
1 2
1 3
3 4
4 1
就会卡住,所以要在最后循环结束存储