> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/hashtable/bipartite.md).

# Bipartite

Hard

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.

```java
public class Solution {
  public boolean isBipartite(List<GraphNode> graph) {
    HashMap<GraphNode, Integer> visited = new HashMap<>();
    for (GraphNode node : graph){
      if (!BFS(node, visited)){
        return false;
      }
    }
    return true;
  }

  private boolean BFS(GraphNode node, HashMap<GraphNode, Integer> visited){
    //if already visited, skip
    if (visited.containsKey(node)) return true;
    
    //BFS queue
    Queue<GraphNode> queue = new LinkedList<GraphNode>();
    queue.offer(node);
    visited.put(node, 0);
    
    //start coloring
    //first node color is 0
    while(!queue.isEmpty()){
      GraphNode cur = queue.poll();

      //current color
      int curGroup = visited.get(cur);
      //neighbors nodes should be the opposite color of current node
      int neiGroup = curGroup == 0 ? 1 : 0;
      
      for(GraphNode nei : cur.neighbors){
        //insert new nodes with color
        if (!visited.containsKey(nei)){
          visited.put(nei, neiGroup);
          queue.offer(nei);
        } else if (visited.get(nei) != neiGroup){
        //if previously seen, but has same color as current node.
        //Means there exists an edge between two nodes of same group
          return false;
        }
      }
    }
    return true;
  }
}
```

**Time Complexity:** O(N^2) BFS each node

**Space Complexity:** O(N) Hashmap and Queue