给你一个无向图， 让你判断这是不是一个二分图。
二分图的标准：可以把这个图的点分成两堆，试每条边都连接这两个堆里的点，而一个堆里的点不能相连。
无向图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 { 9 to[cnt] = y; 10 next[cnt] = head[x]; 11 head[x] = cnt++; 12 } 13 14 bool dfs(int u, int c) 15 { 16 int i, v; 17 color[u] = c; 18 for(i = head[u]; i != -1; i = next[i]) 19 { 20 v = to[i]; 21 if(color[v] == c) return 0; 22 if(color[v] == 0 && !dfs(v, -c)) return 0; 23 } 24 return 1; 25 } 26 27 bool solve() 28 { 29 int i; 30 for(i = 1; i <= n; i++) 31 if(color[i] == 0 && !dfs(i, 1)) 32 return 0; 33 return 1; 34 } 35 36 int main() 37 { 38 int i, x, y; 39 scanf("%d %d", &n, &e); 40 memset(head, -1, sizeof(head)); 41 for(i = 1; i <= e; i++) 42 { 43 scanf("%d %d", &x, &y); 44 add(x, y); 45 add(y, x); 46 } 47 if(solve()) printf("YES"); 48 else printf("NO"); 49 return 0; 50 }
——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() { 14 #ifdef DEBUG 15 freopen("in.txt", "r", stdin); 16 #else 17 //freopen(); 18 //freopen(); 19 #endif 20 } 21 22 inline int get_num() { 23 int k = 0, f = 1; 24 char c = getchar(); 25 for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; 26 for(; isdigit(c); c = getchar()) k = k * 10 + c - '0'; 27 return k * f; 28 } 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 { 36 to[cnt] = y; 37 next[cnt] = head[x]; 38 head[x] = cnt++; 39 } 40 41 int main() 42 { 43 int i, j, x, y, u, v; 44 n = get_num(); 45 m = get_num(); 46 memset(head, -1, sizeof(head)); 47 for(i = 1; i <= m; i++) 48 { 49 x = get_num(); 50 y = get_num(); 51 add(x, y); 52 add(y, x); 53 } 54 memset(color, -1, sizeof(color)); 55 q.push(1); 56 color[1] = 0; 57 while(!q.empty()) 58 { 59 u = q.front(); 60 q.pop(); 61 for(i = head[u]; i != -1; i = next[i]) 62 { 63 v = to[i]; 64 if(color[v] == color[u]) 65 { 66 printf("WRONG!"); 67 return 0; 68 } 69 if(color[v] == -1) 70 { 71 color[v] = color[u] ^ 1; 72 q.push(v); 73 } 74 } 75 } 76 return 0; 77 }
——并查集
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() { 14 #ifdef DEBUG 15 freopen("in.txt", "r", stdin); 16 #else 17 //freopen(); 18 //freopen(); 19 #endif 20 } 21 22 inline int get_num() { 23 int k = 0, f = 1; 24 char c = getchar(); 25 for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; 26 for(; isdigit(c); c = getchar()) k = k * 10 + c - '0'; 27 return k * f; 28 } 29 30 int n, m; 31 int f[MAXN]; 32 33 inline int find(int x) 34 { 35 return x == f[x] ? x : f[x] = find(f[x]); 36 } 37 38 int main() 39 { 40 int i, j, x, y, fx, fy; 41 n = get_num(); 42 m = get_num(); 43 for(i = 1; i <= n * 2; i++) f[i] = i; 44 for(i = 1; i <= m; i++) 45 { 46 x = get_num(); 47 y = get_num(); 48 fx = find(2 * x - 1); 49 fy = find(2 * y); 50 //一个染白则另一个染黑 51 f[fx] = fy; 52 fx = find(2 * x); 53 fy = find(2 * y - 1); 54 //一个染黑则另一个染白 55 f[fx] = fy; 56 } 57 for(i = 1; i <= n; i++) 58 if(find(i * 2) == find(i * 2 - 1)) 59 { 60 printf("WRONG!"); 61 return 0; 62 } 63 return 0; 64 }