二分图的判定

dfs染色法, 若存在起点与终点颜色一样则不属于二分图,若全部满足不相同则是, 颜色只有两种.也就是相邻的点颜色属于不同种即可

例题：https://hihocoder.com/problemset/problem/1121

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define mem(a, b) memset(a, b, sizeof(a))
 4 
 5 int n, m;
 6 int head[10010], cnt;
 7 int color[10010];
 8 int flag, c;
 9 
10 struct Edge
11 {
12     int to, next;
13 }edge[40010 * 2];
14 
15 void add(int a, int b)
16 {
17     edge[++ cnt].to = b;
18     edge[cnt].next = head[a];
19     head[a] = cnt;
20 }
21 
22 void dfs(int now, int c)
23 {
24     color[now] = c;     //染成c
25     for(int i = head[now]; i != -1; i = edge[i].next)
26     { 
27         int to = edge[i].to;
28         if(color[to] == c)
29         {
30             flag = 0;
31             return ;
32         }
33         if(!color[to])
34             dfs(to, -c);
35         if(!flag)
36             return ;
37     }
38     return ;
39 }
40 
41 int main()
42 {
43     int T;
44     scanf("%d", &T);
45     while(T --)
46     {
47         flag = 1;
48         cnt = 0;
49         c = 1;
50         mem(head, -1);
51         mem(color, 0);   //染色初始化为0代表没有染色
52         scanf("%d%d", &n, &m);
53         for(int i = 1; i <= m; i ++)
54         {
55             int a, b;
56             scanf("%d%d", &a, &b);
57             add(a, b);
58             add(b, a);
59         }
60         for(int i = 1; i <= n; i ++)//防止不连通图
61             if(!color[i])
62             {
63                 dfs(i, c);
64                 if(!flag)
65                     break;
66             }
67         if(flag)
68             printf("Correct
");
69         else
70             printf("Wrong
");
71     }
72     return 0;
73 }

View Code