1 /*
2 题意：给一个n个点,m条边的无向图,要求给m条边定方向,使得每个定点的出入度之差的绝对值小于等于1. 输出任意一种结果
3 图论：一个图，必定存在偶数个奇度顶点。那么从一个奇度定点深搜，当碰到另外一个奇度顶点时结束，这样能保证度数差<=1
3.5 详细解释：http://blog.csdn.net/ZSGG_ACM/article/details/47287681
4 */
5 /************************************************
6 * Author :Running_Time
7 * Created Time :2015-8-5 18:55:37
8 * File Name :F.cpp
9 ************************************************/
10 #pragma comment (linker, "/STACK:1024000000,1024000000")
11 #include <cstdio>
12 #include <algorithm>
13 #include <iostream>
14 #include <sstream>
15 #include <cstring>
16 #include <cmath>
17 #include <string>
18 #include <vector>
19 #include <queue>
20 #include <deque>
21 #include <stack>
22 #include <list>
23 #include <map>
24 #include <set>
25 #include <bitset>
26 #include <cstdlib>
27 #include <ctime>
28 using namespace std;
29
30 #define lson l, mid, rt << 1
31 #define rson mid + 1, r, rt << 1 | 1
32 typedef long long ll;
33 const int MAXN = 1e5 + 10;
34 const int INF = 0x3f3f3f3f;
35 const int MOD = 1e9 + 7;
36 struct Edge {
37 int v, nex, dir;
38 }e[MAXN*6];
39 int head[MAXN];
40 int deg[MAXN];
41 int n, m, tot;
42
43 void init(void) {
44 tot = 0;
45 memset (head, -1, sizeof (head));
46 memset (deg, 0, sizeof (deg));
47 }
48
49 void add_edge(int u, int v) {
50 e[tot].v = v;
51 e[tot].nex = head[u];
52 e[tot].dir = 0;
53 head[u] = tot++;
54 }
55
56 bool DFS(int u) {
57 for (int &i=head[u]; ~i; i=e[i].nex) {
58 int v = e[i].v;
59 int dir = e[i].dir ^ e[i^1].dir;
60 if (dir) continue;
61 e[i].dir = 1;
62 if (deg[v]) {
63 deg[v] = 0; return true;
64 }
65 if (DFS (v)) return true;
66 }
67 return false;
68 }
69
70 void work(void) {
71 for (int i=1; i<=n; ++i) {
72 if (deg[i]) {
73 deg[i] = 0; DFS (i);
74 }
75 }
76 for (int i=1; i<=n; ++i) {
77 while (~head[i]) DFS (i);
78 }
79 for (int i=0; i<tot; i+=2) {
80 if (e[i].dir) puts ("1");
81 else puts ("0");
82 }
83 }
84
85 int main(void) { //HDOJ 5348 MZL's endless loop
86 int T; scanf ("%d", &T);
87 while (T--) {
88 init ();
89 scanf ("%d%d", &n, &m);
90 for (int i=1; i<=m; ++i) {
91 int u, v; scanf ("%d%d", &u, &v);
92 deg[u] ^= 1; deg[v] ^= 1;
93 add_edge (u, v); add_edge (v, u);
94 }
95 work ();
96 }
97
98 return 0;
99 }
1 /************************************************ 2 * Author :Running_Time 3 * Created Time :2015-8-5 18:55:37 4 * File Name :F.cpp 5 ************************************************/ 6 #pragma comment (linker, "/STACK:1024000000,1024000000") 7 #include <cstdio> 8 #include <algorithm> 9 #include <iostream> 10 #include <sstream> 11 #include <cstring> 12 #include <cmath> 13 #include <string> 14 #include <vector> 15 #include <queue> 16 #include <deque> 17 #include <stack> 18 #include <list> 19 #include <map> 20 #include <set> 21 #include <bitset> 22 #include <cstdlib> 23 #include <ctime> 24 using namespace std; 25 26 #define lson l, mid, rt << 1 27 #define rson mid + 1, r, rt << 1 | 1 28 typedef long long ll; 29 const int MAXN = 1e5 + 10; 30 const int INF = 0x3f3f3f3f; 31 const int MOD = 1e9 + 7; 32 struct Edge { 33 int v, nex, vis; 34 }e[MAXN*6]; 35 int head[MAXN]; 36 int deg[MAXN]; 37 int ans[MAXN*6]; 38 int n, m, tot; 39 40 void init(void) { 41 tot = 0; 42 memset (head, -1, sizeof (head)); 43 memset (deg, 0, sizeof (deg)); 44 } 45 46 void add_edge(int u, int v) { 47 e[tot].v = v; 48 e[tot].nex = head[u]; 49 e[tot].vis = 0; 50 head[u] = tot++; 51 } 52 53 void DFS(int u) { 54 for (int &i=head[u]; ~i; ) { 55 int v = e[i].v; 56 if (e[i].vis) { 57 i = e[i].nex; continue; 58 } 59 e[i].vis = 1; e[i^1].vis = 1; 60 ans[i>>1] = i & 1; 61 deg[u]--; deg[v]--; 62 i = e[i].nex; 63 DFS (v); 64 } 65 } 66 67 void patch(void) { 68 int pre = -1; 69 for (int i=1; i<=n; ++i) { 70 if (deg[i] & 1) { 71 if (pre == -1) { 72 pre = i; 73 } 74 else { 75 add_edge (pre, i); add_edge (i, pre); 76 deg[pre]++; deg[i]++; 77 pre = -1; 78 } 79 } 80 } 81 } 82 83 void work(void) { 84 patch (); 85 for (int i=1; i<=n; ++i) { 86 if (deg[i]) DFS (i); 87 } 88 for (int i=0; i<m; ++i) printf ("%d ", ans[i]); 89 } 90 91 int main(void) { 92 int T; scanf ("%d", &T); 93 while (T--) { 94 init (); 95 scanf ("%d%d", &n, &m); 96 for (int i=1; i<=m; ++i) { 97 int u, v; scanf ("%d%d", &u, &v); 98 deg[u]++; deg[v]++; 99 add_edge (u, v); add_edge (v, u); 100 } 101 work (); 102 } 103 104 return 0; 105 }