【HDOJ】1814 Peaceful Commission

 1 /* 1814 */
 2 #include <iostream>
 3 #include <vector>
 4 #include <algorithm>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <cstdlib>
 8 using namespace std;
 9 
10 #define MAXN 8005
11 
12 vector<int> vc[MAXN*2];
13 bool visit[MAXN*2];
14 int S[MAXN*2], top;
15 int n, m;
16 
17 bool dfs(int u) {
18     if (visit[u^1])    return false;
19     if (visit[u])    return true;
20     
21     visit[u] = true;
22     S[top++] = u;
23     for (int i=0; i<vc[u].size(); ++i) {
24         if (!dfs(vc[u][i]))
25             return false;
26     }
27     return true;
28 }
29 
30 int main() {
31     int ii, jj;
32     int i, j, k;
33     bool flag;
34     
35     #ifndef ONLINE_JUDGE
36         freopen("data.in", "r", stdin);
37     #endif
38     
39     while (scanf("%d %d", &n, &m) != EOF) {
40         k = n+n;
41         for (i=0; i<k; ++i)
42             vc[i].clear();
43         memset(visit, false, sizeof(bool)*k);
44         while (m--) {
45             scanf("%d %d", &i, &j);
46             --i;
47             --j;
48             ii = (i&1) ? i-1:i+1;
49             jj = (j&1) ? j-1:j+1;
50             vc[i].push_back(jj);
51             vc[j].push_back(ii);
52         }
53         flag = true;
54         for (i=0; i<k; i+=2) {
55             if (! (visit[i]||visit[i+1])) {
56                 top = 0;
57                 if (!dfs(i)) {
58                     while (top--)
59                         visit[S[top]] = false;
60                     if (!dfs(i+1)) {
61                         flag = false;
62                         break;
63                     }
64                 }
65             }
66         }
67         if (flag) {
68             for (i=0; i<k; ++i)
69                 if (visit[i])
70                     printf("%d\n", i+1);
71         } else {
72             puts("NIE");
73         }
74     }
75     
76     return 0;
77 }