【模板】判断二分图

给你一个无向图， 让你判断这是不是一个二分图。

二分图的标准：可以把这个图的点分成两堆，试每条边都连接这两个堆里的点，而一个堆里的点不能相连。

无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。（？？？什么意思？？？）

语文不好，看图吧。

就这个意思。

而现在然你自己判断该怎么判断。

——看代码就能看懂（dfs版）

1 #include <cstdio> 2 #include <cstring> 3 4 int n, e, cnt; 5 int head[1001], next[1001], to[1001], color[1001]; 6 7 void add(int x, int y) 8 13 14 bool dfs(int u, int c) 15 24 return 1; 25 } 26 27 bool solve() 28 35 36 int main() 37 47 if(solve()) printf("YES"); 48 else printf("NO"); 49 return 0; 50 }
View Code

——bfs版

1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib> 10 # define MAXN 2333 11 using namespace std; 12 13 inline void File() 21 22 inline int get_num() 29 30 int n, m, cnt; 31 int head[MAXN], next[MAXN], to[MAXN], color[MAXN]; 32 queue <int> q; 33 34 inline void add(int x, int y) 35 40 41 int main() 42 54 memset(color, 1, sizeof(color)); 55 q.push(1); 56 color[1] = 0; 57 while(!q.empty()) 58 69 if(color[v] == 1) 70 74 } 75 } 76 return 0; 77 }
View Code

——并查集

1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib> 10 # define MAXN 233 11 using namespace std; 12 13 inline void File() 21 22 inline int get_num() 29 30 int n, m; 31 int f[MAXN]; 32 33 inline int find(int x) 34 37 38 int main() 39 57 for(i = 1; i <= n; i++) 58 if(find(i * 2) == find(i * 2 1)) 59 return 0; 64 }
View Code

上一篇： 遇到的Docker常用命令

下一篇：NOIP2013D1T3货车运输（最大生成树+倍增lca）

---

二分图 模板