Divide Groups（分组）（二分图染色）

题目大意是说输入数字n

然后告诉你第i个人都认识谁？

让你把这些人分成两堆，使这每个堆里的人都互相认识。

做法：把不是互相认识的人建立一条边，则构建二分图，两堆的人肯定都互相认识，也就是说，互相认识的两个人肯定不相连。

——代码

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 int n, cnt;
 7 int head[200001], to[200001], next[200001], color[101];
 8 bool know[101][101];
 9 
10 void add(int x, int y)
11 {
12     to[cnt] = y;
13     next[cnt] = head[x];
14     head[x] = cnt++;
15 }
16 //把点染成1或-1 
17 bool dfs(int u, int c)
18 {
19     int i, v;
20     color[u] = c;
21     for(i = head[u]; i != - 1; i = next[i])
22     {
23         v = to[i];
24         if(color[v] == c) return 0;
25         if(color[v] == 0 && !dfs(v, -c)) return 0;
26     }
27     return 1;
28 }
29 
30 bool solve()
31 {
32     int i;
33     for(i = 1; i <= n; i++)
34      if(color[i] == 0 && !dfs(i, 1))
35       return 0;
36     return 1;
37 }
38 
39 int main()
40 {
41     int i, j, x;
42     while(~scanf("%d", &n))
43     {
44         memset(know, 0, sizeof(know));
45         memset(color, 0, sizeof(color));
46         for(i = 1; i <= n; i++)
47           while(scanf("%d", &x) && x)
48           know[i][x] = 1;
49         memset(head, -1, sizeof(head));
50         for(i = 1; i <= n; i++)
51          for(j = i + 1; j <= n; j++)
52           if(!know[i][j] || !know[j][i])
53           {
54               add(i, j);
55               add(j, i);
56           }
57         if(solve()) printf("YES
");
58         else printf("NO
");
59     }
60     return 0;
61 }

View Code