Determine if an undirected graph is bipartite. A bipartite graph is one in which the nodes can be divided into two groups such that no nodes have direct edges to other nodes in the same group.

Examples

1 -- 2

/   

3 -- 4

is bipartite (1, 3 in group 1 and 2, 4 in group 2).

1 -- 2

/   \|

3 -- 4

is not bipartite.

Assumptions

• The graph is represented by a list of nodes, and the list of nodes is not null.

Solution: 用0和一标记两个group，每个node的neighbor必须在跟node不同的group，否则返回false

  public boolean isBipartite(List<GraphNode> graph) {
  //用0和1标记两个group
    Map<GraphNode, Integer> hashmap = new HashMap<>();
    Queue<GraphNode> queue = new LinkedList<>();
    //要遍历graph，因为有可能不连通
    for (GraphNode node : graph) {
      if (hashmap.containsKey(node)) {
        continue;
      }
      queue.offer(node);
      hashmap.put(node, 0);
      while (!queue.isEmpty()) {
        GraphNode cur = queue.poll();
        int curGroup = hashmap.get(cur);
        //neighborGroup必须与curGroup不同
        int neighborGroup = curGroup == 0 ? 1 : 0;
        for (GraphNode neighbor : cur.neighbors) {
          if (!hashmap.containsKey(neighbor)) {
            hashmap.put(neighbor, neighborGroup);
            queue.offer(neighbor);
          } else if (hashmap.get(neighbor) != neighborGroup) {
            return false;
          }
        }
      }
    }
    return true;
  }