都忘了欧拉路径是什么了。。
用dfs搜 标记边 刚开始直接从I-N搜 直接超时 2了 先找符合起点和终点的点搜 即度数是奇数
d单dfs也超了 后来换了个姿势。。
/*
ID: shangca2
LANG: C++
TASK: fence
*/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int w[][],n,p[],flag,m,de[],t;
void dfs(int u,int d)
{
for(int v = ; v <= m ; v++)
{
if(w[u][v])
{
w[u][v]--;
w[v][u]--;
dfs(v,d+);
}
}
p[t++] = u;
return ;
}
int main()
{
freopen("fence.in","r",stdin);
freopen("fence.out","w",stdout);
int i,u,v,st;
cin>>n;
m = ;
for(i= ; i <= n ; i++)
{
scanf("%d%d",&u,&v);
m = max(m,max(u,v));
de[u]++;
de[v]++;
w[u][v]++;
w[v][u]++;
}
int f = ;
for(i = ; i <= m ; i++)
{
if(de[i]%!=)
{
st = i;
break;
}
if(f&&de[i])
{
f = ;
st = i;
}
}
dfs(st,);
for(i = t-; i >= ; i--)
printf("%d\n",p[i]);
return ;
}