1106. Two Teams（dfs 染色）

结点染色当前结点染为黑朋友染为白依次染下去

这题是为二分图打基础吧

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 using namespace std;
 8 vector<int>ed[110];
 9 int vis[110],num;
10 void dfs(int u,int c)
11 {
12     int i;
13     vis[u] = c;
14     if(c==1)
15     num++;
16     for(i = 0 ; i < (int)ed[u].size() ; i++)
17     {
18         int v = ed[u][i];
19         if(!vis[v])
20         dfs(v,-c);
21     }
22 }
23 int main()
24 {
25     int i,a,n;
26     scanf("%d",&n);
27     for(i = 1; i <= n ; i++)
28     {
29         while(scanf("%d",&a)&&a)
30         {
31             ed[i].push_back(a);
32         }
33     }
34     for(i = 1; i <= n ; i++)
35     {
36         if(!vis[i])
37         dfs(i,1);
38     }
39     printf("%d
",num);
40     int k=0;
41     for(i = 1; i <= n ; i++)
42     {
43         if(vis[i]==1)
44         {
45             if(k)
46             printf(" ");
47             printf("%d",i);
48             k++;
49         }
50     }
51     puts("");
52     return 0;
53 }

View Code