Checking whether a Graph is Bipartite

题目链接：pdf

题目给一个无向图，判定这个图是否是二分图。

所谓二分图就是，用可以两种颜色给这个图的所有节点染色，并且满足相邻两个点颜色不同。

思路：

模拟染色过程，遍历所有点，如果这个点没有被染色，那么用BFS从这个点开始染色，当出现两个点颜色相同，说明这个图不是二分图。如果这个点已经被染色过，那么判断一下和这个点直接相连的点和它的颜色是否相同。

// Sun May 14 21:24:26 CST 2017
// Sun May 14 21:43:44 CST 2017


/*
  二分图判定
*/

#include <iostream>
#include <vector>
#include <queue>

using std::vector;
using std::queue;

int bipartite(vector<vector<int> > &adj) {
  int result = 1;
  vector<int> color(adj.size(), -1);
  queue<int> que;

  for (size_t i = 0; i < adj.size(); ++i) {
    if (-1 == color[i]) {
      color[i] =1;
      que.push(i);

      while (!que.empty()) {
	int cur = que.front();
	que.pop();

	for (auto v : adj[cur]) {
	  if (-1 == color[v]) {
	    color[v] = 1 - color[cur];
	  }
	  else if (color[v] == color[cur]) {
	    return 0;
	  }
	}
      }
    }
    else {
      for (auto v : adj[i]) {
	if (color[v] == color[i]) {
	  return 0;
	}
      }
    }
  }
  
  return result;
}

int main() {
  int n, m;
  while (std::cin >> n >> m) {
    vector<vector<int> > adj(n, vector<int>());
    for (int i = 0; i < m; i++) {
      int x, y;
      std::cin >> x >> y;
      adj[x - 1].push_back(y - 1);
      adj[y - 1].push_back(x - 1);
    }
    std::cout << bipartite(adj) << "\n";
  }
}