二分图判定（图论基础）

哇咔咔，终于开始接触图论了，心情有点小激动；

例题的大概意思就是问是否最多用两种颜色进行染色？

下面的第一个代码针对的是连通图：

 1 #include<iostream>
 2 #include<vector>
 3 #include<cstdio>
 4 using namespace std;
 5 vector<int>G[1000];
 6 int color[1000] = { 0 };
 7 bool solve(int v, int c)
 8 {
 9     color[v] = c;
10     for (int i = 0; i < G[v].size(); i++)
11     {
12         if (color[G[v][i]] == c) return false;
13         if (color[G[v][i]] == 0 && !solve(G[v][i], -c)) return false;
14     }
15     return true;
16 }
17 int main()
18 {
19     int V, E;
20     scanf("%d",&E);
21     for (int i = 0; i < E; i++)
22     {
23         int s, t;
24         scanf("%d%d", &s, &t);
25         G[s].push_back(t);
26     }
27     cout << solve(0, 1) << endl;
28     return 0;
29 }

就是根据dfs的思路进行标记和判定

如果不是连通图的话，可以通过循环遍历来进行判断