给你一个无向图， 让你判断这是不是一个二分图。
二分图的标准：可以把这个图的点分成两堆，试每条边都连接这两个堆里的点，而一个堆里的点不能相连。
无向图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
上一篇：【模板】左偏树
下一篇：求逆序对（树状数组）
模板 二分图
