题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5348
题意：给你一个无向图，要你将无向图的边变成有向边，使得得到的图，出度和入度差的绝对值小于等于1，如果无解输出-1
解：考虑奇数度的点一定会成对出现（因为所有度数和肯定是偶数个->一条边对应两度~），那么我们可以将奇数度的点两两一连消除掉（两奇数度点的出度入读差的绝对值都为1， 路径上的点的差绝对值为0）
然后偶数度的点可以成环，那么可以搜出所有的环
/*
* Problem:
* Author: SHJWUDP
* Created Time: 2015/8/5 星期三 16:29:03
* File Name: 1006.cpp
* State:
* Memo:
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> using namespace std; struct Edge {
int u, v;
}; int n, m;
vector<Edge> edges;
vector<vector<int> > G;
vector<int> cur, dg, vis, ans;
void init(int N, int M) {
edges.clear();
G.assign(N, vector<int>());
cur.assign(N, );
vis.assign(M<<, );
ans.assign(M, -);
dg.assign(N, );
}
void addEdge(int u, int v) {
edges.push_back((Edge){u, v});
G[u].push_back(edges.size()-);
}
void euler(int u) {
while(cur[u]<(int)G[u].size()) {
int i=G[u][cur[u]];
if(vis[i]) {
cur[u]++; continue;
}
Edge & e=edges[i];
if(i & ) ans[i>>]=;
else ans[i>>]=;
vis[i]=vis[i^]=;
cur[u]++;
dg[e.u]--; dg[e.v]--;
u=e.v;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
init(n+, m+);
for(int i=; i<m; i++) {
int a, b;
scanf("%d%d", &a, &b);
addEdge(a, b);
addEdge(b, a);
dg[a]++; dg[b]++;
}
for(int i=; i<=n; i++) {
if(dg[i] & ) euler(i);
}
for(int i=; i<=n; i++) {
if(dg[i] > ) euler(i);
}
for(int i=; i<m; i++) {
printf("%d\n", ans[i]);
}
}
return ;
}
hdu5348