HDU 1814 模板题 2-sat

敲模板做的，不知道怎么就对了，注意一下建边即可···
贴代码：
 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 #define N 16005
 5 struct twosat
 6 {
 7     int n;
 8     vector<int> g[N*2];
 9     bool vis[N*2];
10     int path[N*2];
11     int c;
12 
13     bool dfs(int x)
14     {
15         if(vis[x^1]) return false;
16         if(vis[x]) return true;
17         vis[x] =true;
18         path[c++] = x;
19         for(int i=0; i<g[x].size(); ++i)
20             if(!dfs(g[x][i])) return false;
21         return true;
22     }
23     void init(int n)
24     {
25         this->n = n;
26         for(int i=0; i<n*2; ++i)
27         {
28             g[i].clear();
29             vis[i] =0;
30         }
31     }
32 
33     void addEdge(int x,int y)
34     {
35         g[x].push_back(y^1);
36         g[y].push_back(x^1);
37     }
38 
39     bool solve()
40     {
41         for(int i=0; i<2*n; i += 2)
42         {
43             if(!vis[i] && !vis[i+1])
44             {
45                 c =0;
46                 if(!dfs(i))
47                 {
48                     while(c > 0) vis[path[--c]] = false;
49                     if(!dfs(i+1)) return false;
50                 }
51             }
52         }
53         return true;
54     }
55 
56 };
57 twosat ts;
58 int main()
59 {
60 //    freopen("in.c","r",stdin);
61     int n,m;
62     while(~scanf("%d%d",&n,&m))
63     {
64         ts.init(n);
65         for(int i=0; i<m; ++i)
66         {
67             int u,v;
68             scanf("%d%d",&u,&v);
69             --u,--v;
70             ts.addEdge(u,v);
71         }
72         if(ts.solve())
73         {
74             for(int i=0; i<2*n; i+=2)
75                 printf("%d
",(ts.vis[i]?i:i^1)+1);
76         }
77         else printf("NIE
");
78     }
79     return 0;
80 }
View Code