Medium · Graphs

Is Graph Bipartite?

Given an undirected graph as adjacency lists adj (adj[v] lists the neighbors of node v, nodes 0..n−1), return true if its nodes can be split into two groups so that every edge joins nodes from different groups, otherwise false.

Examples

Example 1

{
  "adj": [
    [1, 3],
    [0, 2],
    [1, 3],
    [0, 2]
  ],
  "pos": [
    [176, 44],
    [275, 143],
    [176, 242],
    [77, 143]
  ]
}

Output: bipartite

Example 2

{
  "adj": [
    [1, 2],
    [0, 2],
    [0, 1]
  ],
  "pos": [
    [176, 44],
    [262, 193],
    [90, 193]
  ]
}

Output: not bipartite

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.