题目链接：
题目描述：
给出一个无向图(有环，有重边)，包含n个顶点，m条边，问能否给m条边指定方向，使每个顶点都满足abs(出度-入度)<2。如果能输出任意一种合法方案。
解题思路：
其实仔细考虑一下，每个无向图都会存在合法方案的。证明：度数和为奇数的点只能为起点或者终点，度数为偶数的只能是环上的起点或者终点或者是中间点。有m条边，一共有2*m个端点。所以呢？当然是度数和为奇数的个肯定是偶数个，任意两个相结合都可以形成一条路。并不会有两条路的起点相同或者终点相同咯。
由上可知所给的无向图是由若干条路径和若干个环组成的，我们可以对每个点进行dfs，当前遍历的点入度大于出度就正向遍历，否则反向遍历，直到遍历不到边为止。每遍历到一条边就将其删去，遇到环就回溯到环的起点。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#pragma comment (linker, "/STACK:102400000,102400000")
using namespace std; const int maxn = ;
struct node
{
int to, next, id;
}edge[maxn*];
int head[maxn], du[][maxn], sum[maxn];
int vis[maxn*], ans[maxn*], tot; void init ()
{
tot = ;
memset (head, -, sizeof(head));
memset (du, , sizeof(du));
//du[0][i]i点的入度，du[1][i]i的出度
memset (sum, , sizeof(sum));
//sum[i]i的度数总和
memset (vis, , sizeof(vis));
//边是否遍历过
memset (ans, -, sizeof(ans));
}
void Add (int from, int to, int id)
{
edge[tot].to = to;
edge[tot].id = id;
edge[tot].next = head[from];
head[from] = tot ++;
}
void dfs (int u, int y)
{
for (int i=head[u]; i!=-; i=edge[i].next)
{
if (vis[i])
{//当前边已经被访问过
head[u] = edge[i].next;
//删边
continue;
}
int v = edge[i].to;
if (v!=u && du[y][v]<du[y^][v])
//当前点若和u相连，abs(出度-入度)>1
continue;
vis[i] = vis[i^] = ;
if (i % )
ans[i/] = y^;
else
ans[i/] = y;
du[y][u] ++;
du[y^][v] ++;
head[u] = edge[i].next;
dfs (v, y);
break;
}
}
int main ()
{
int t, n, m;
scanf ("%d", &t);
while (t --)
{
scanf ("%d %d", &n, &m);
init ();
for (int i=; i<m; i++)
{
int u, v;
scanf ("%d %d", &u, &v);
Add (u, v, i);
Add (v, u, i);
sum [u] ++;
sum [v] ++;
}
for (int i=; i<=n; i++)
{
while (du[][i] + du[][i] < sum[i])
{
if (du[][i] <= du[][i])
dfs (i, );
else
dfs (i, );
}
}
for (int i=; i<m; i++)
printf ("%d\n", ans[i]);
}
return ;
}
