原题链接
考察:欧拉路径,离散化
思路:
??定睛一看这不欧拉路径吗,然后套板子即可....
Code
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;
int n,h[N<<1],idx,tot,id[N],d[N<<1];
int ans[N<<1],cnt;
map<int,int> vis;
struct Road{
int to,ne;
bool exist;
}road[N<<1];
void add(int a,int b)
{
road[idx].exist = 1,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++;
}
void dfs(int u)
{
for(int& i=h[u];~i;)
{
if(!road[i].exist)
{
i = road[i].ne;
continue;
}
int v = road[i].to;
road[i^1].exist = 0;
i = road[i].ne;
dfs(v);
ans[++cnt] = id[v];
}
}
int main()
{
scanf("%d",&n);
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(!vis.count(a)) id[++tot] = a,vis[a] = tot;
if(!vis.count(b)) id[++tot] = b,vis[b] = tot;
add(vis[a],vis[b]),add(vis[b],vis[a]);
d[vis[a]]++;
d[vis[b]]++;
}
for(int i=1;i<=tot;i++)
if(d[i]&1)
{
dfs(i);
ans[++cnt] = id[i];
break;
}
for(int i=cnt;i>=1;i--)
printf("%d ",ans[i]);
return 0;
}