二分图

如果两个结点由于某些性质不能归属到一个集合，那么在这两个点之间连一条边。在遍历所有点对，建图之后。如果通过染色法成功对图进行染色，那么这个图就是一个二分图，否则这个图不是二分图。下面是染色法判断二分图的模板。

  1. const int N = 1010, M = N * N;
  3. int color[N];
  4. int h[N], e[M], ne[M], idx;
  6. bool dfs(int u, int c) {
  7.     color[u] = c;
  9.     for(int i = h[u]; ~i; i = ne[i]) {
  10.         int j = e[i];
  11.         if(color[j] == c) {
  12.             return false;
  13.         }
  14.         if(color[j] == -1 && !dfs(j, 1 - c)) {
  15.             return false;
  16.         }
  17.     }
  19.     return true;
  20. }
  22. bool ok = true;
  23. memset(color, -1, sizeof color);
  24. for(int i = 0; i < n; i++) {
  25.     if(color[i] == -1 && !dfs(i, 0)) {
  26.         ok = false;
  27.         break;
  28.     }
  29. }