有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。
一共两个子任务：
第一行一个整数 tt，表示子任务编号。t∈{1,2}t∈{1,2}，如果 t=1t=1 则表示处理无向图的情况，如果 t=2t=2 则表示处理有向图的情况。
第二行两个整数 n,mn,m，表示图的结点数和边数。
接下来 mm 行中，第 ii 行两个整数 vi,uivi,ui，表示第 ii 条边（从 11 开始编号）。保证 1≤vi,ui≤n1≤vi,ui≤n。
图中可能有重边也可能有自环。
如果不可以一笔画，输出一行 “NO”。
否则，输出一行 “YES”，接下来一行输出一组方案。
1 3 3 1 2 2 3 1 3
YES 1 2 -3
2 5 6 2 3 2 5 3 4 1 2 4 2 5 1
YES 4 1 3 5 2 6
1≤n≤105,0≤m≤2×1051≤n≤105,0≤m≤2×105
时间限制：1s1s
空间限制：256MB
说是模板题，然而并不容易写啊～坑的数据太多。。。
要进行各种优化。。。不然会TLE。。。UOJ Extra Test 也有一组坑点，一定要注意下！
另外：本题有重边和自环。。。
代码用的是基本法（套圈）蛤蛤蛤
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<cstring>
#include<map>
using namespace std;
int t,n,m,x,y,cur;
int head[1000010],sum[1000010],adj[1000010],cnt=1;
bool vis[1000010];
struct sdt
{
int u,v,nxt;
}e[4001000];
stack<int>s;
inline int read()
{
int x=0;char c=getchar();
while(c<48||c>57)c=getchar();
while(c>47&&c<58)x*=10,x+=c-48,c=getchar();
return x;
}
inline void add(int x,int y)
{
e[++cnt].u=x;
e[cnt].v=y;
e[cnt].nxt=head[x];
head[x]=cnt;
adj[x]=head[x];
}
inline int gets(int x)
{
return x%2==0 ? x/2 : -x/2 ;
}
void dfs1(int x)
{
while(adj[x])
{
if(!vis[adj[x]])
{
vis[adj[x]]=1;
vis[adj[x]^1]=1;
int k=adj[x];
dfs1(e[k].v);
s.push(gets(k));
cur++;
}
else adj[x]=e[adj[x]].nxt;
}
}
inline bool solve1()
{
n=read();
m=read();
for(int i=1;i<=m;i++)
{
x=read();
y=read();
add(x,y);
add(y,x);
sum[x]++;
sum[y]++;
}
for(int i=1;i<=n;i++)
{
if(sum[i]%2)return 0;
}
for(int i=1;i<=n;i++)
{
if(sum[i])
{
dfs1(i);
break;
}
}
if(cur!=m)return 0; else return 1;
}
void dfs2(int x)
{
while(adj[x])
{
if(!vis[adj[x]])
{
vis[adj[x]]=1;
int k=adj[x];
dfs2(e[k].v);
s.push(k-1);
cur++;
}
else adj[x]=e[adj[x]].nxt;
}
}
inline bool solve2()
{
n=read();
m=read();
for(int i=1;i<=m;i++)
{
x=read();
y=read();
add(x,y);
sum[x]++;
sum[y]--;
}
for(int i=1;i<=n;i++)
{
if(sum[i])return 0;
}
for(int i=1;i<=n;i++)
{
if(head[i])
{
dfs2(i);
break;
}
}
if(cur!=cnt-1)return 0; else return 1;
}
int main()
{
t=read();
if(t==1)
{
if(solve1()==0)
{
printf("NO\n");
return 0;
}
else
{
printf("YES\n");
while(!s.empty())
{
printf("%d ",s.top());
s.pop();
}
printf("\n");
}
}
else
{
if(solve2()==0)
{
printf("NO\n");
return 0;
}
else
{
printf("YES\n");
while(!s.empty())
{
printf("%d ",s.top());
s.pop();
}
printf("\n");
}
}
return 0;
}
原文：http://www.cnblogs.com/winmt/p/6285950.html