Asked at

Is Graph Bipartite

Medium
VerifiedGraphBFSDFS~25 min

You’re given an undirected graph with n nodes 0..n-1 and edge list edges, where edges[i] = [u, v]. The graph is bipartite if its nodes split into two sets such that every edge crosses between the sets.

Return whether the graph is bipartite. The input arrives as a single object { n, edges }.

Examples

in{ n: 4, edges: [[0,1],[1,2],[2,3],[3,0]] }
outtrue

The even cycle splits into {0,2} and {1,3}.

in{ n: 3, edges: [[0,1],[1,2],[2,0]] }
outfalse

An odd cycle cannot be two-coloured.

Constraints

  • 1 ≤ n ≤ 100
  • Edges are undirected: edges[i] = [u, v]
  • 0 ≤ u, v < n

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.