奇淫巧计,直接将邻接表放到set里做,自动判重、排序,保证输出的是最小字典序
判断欧拉路径的初始条件后直接dfs就行了
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n,m;
set<int> g[N];
int p[N];
int ans[100010],top;
int find(int x) // 并查集
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void dfs(int u){
while(g[u].size()){
int t=*g[u].begin();
g[u].erase(t),g[t].erase(u);
dfs(t);
}
ans[++top]=u;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++) p[i]=i;
while(m--){
int a,b;
scanf("%d%d",&a,&b);
g[a].insert(b),g[b].insert(a);
p[find(a)]=find(b);
}
int s=0;
for(int i=1;i<=n;i++){
if(find(i)!=find(1)){
puts("-1");
return 0;
}
else if(g[i].size()%2) s++;
}
if(s!=0&&s!=2||s==2&&g[1].size()%2==0){
puts("-1");
return 0;
}
dfs(1);
for(int i=top;i;i--) printf("%d ",ans[i]);
return 0;
}
tips:奇淫技巧 ✖,奇技淫巧 √
你们是懂文学的