BDFZOI 二分图的判定

涉及知识：dfs/二分图

提交次数：5

描述

给出一个无向图（无重边/自环），判定其是否是二分图。

*二分图：可以把顶点分成两部分, 每部分之间没有边。

输入第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N <= 5000，M <= 200000）
接下来M行，每行包含三个整数{u,v,w}，表示有一条长度为w的无向边连接结点u、v

输出输出

Yes/No

样例输入

样例输出

Yes

代码：

 1 #include<iostream>
 2 #include<vector>
 3 #include<cstring>
 4 using namespace std;
 5 int n, m;
 6 bool ans=true;
 7 struct edge{
 8     int u, e;
 9     bool visited;
10     edge(int uu, int ee, int vv):u(uu),e(ee),visited(vv){}
11 };
12 vector<edge>v[5005];
13 int color[5005];
14 
15 void dfs(int uu, int c, int step){
16     if(step == 2*m){
17         ans = true;
18         exit(0);
19     }
20     for(int i = 0; i < v[uu].size(); i++){
21         if(v[uu][i].visited) continue;
22         int w = v[uu][i].u;
23         if(color[w]==c){//如果已经有染同色 
24             ans = false;
25             cout<<"No"<<endl;
26             exit(0);
27         }
28         else if(color[w]!=-1&&color[w]!=c)
29             dfs(w,!c,step+1);
30         else if(color[w]==-1){
31             v[uu][i].visited = true;
32             color[w] = !c;
33             dfs(w, !c, step+1);
34         }
35     }
36 }
37 int main(){
38     cin>>n>>m;
39     int i, u, w, e;
40     for(i = 1; i <= m; i++){
41         cin>>u>>w>>e;
42         v[u].push_back(edge(w,e,0));
43         v[w].push_back(edge(u,e,0));
44     }
45     memset(color, -1, sizeof(color));
46     for(i = 1; i <= 5000; i++){
47         if(color[i]==-1){
48             color[i] = 1;
49             dfs(i, 1, 0);
50             if(ans==false) return 0;    
51         }
52     }
53     if(ans==true) cout<<"Yes"<<endl;
54     return 0;
55 }

备注：

如果一个图的所有顶点可以被分为X和Y两个集合，并且所有边的两个顶点恰好一个属于集合X，另一个属于集合Y，即每个集合内的顶点没有边相连，那么此图就是二分图。判断二分图用染色法，dfs或bfs+染色都可以，然而事实证明我的dfs还是很差，写bfs会简单一些。

如果遇到一个顶点，它已经染色，并且颜色不矛盾，就继续从它dfs; 若矛盾，直接输出No；否则染色，继续dfs。

首先是bool型和void型的dfs有本质区别……不能随便换。都return了，退栈后就直接进行到最后了，for循环就没啥用了。就这个问题让我找了好久。

其次是图不一定连通，因此得从不同点搜，并且要注意答案的处理。