noodleProblems/
Is Graph Bipartite?
#147

Is Graph Bipartite?

AlgorithmmediumDepth First SearchBreadth First SearchUnion FindGraph

You are given an undirected graph on n nodes labelled 0 to n - 1, as an adjacency list graph: graph[u] is the array of nodes directly connected to node u. The graph may be disconnected.

A graph is **bipartite** if its nodes can be split into two groups *A* and *B* such that **every edge joins a node in A to a node in B** — no edge lies within a single group. Equivalently, the graph can be 2-coloured with no two adjacent nodes sharing a colour.

Return true if the graph is bipartite, otherwise false.

Example cases

  • odd cycle — not bipartite
    in graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
    out false
    Nodes 0,1,2 form a triangle (an odd cycle), which can never be 2-coloured.
  • even cycle — bipartite
    in graph =
    13
    02
    13
    02
    out true
    A 4-cycle splits into {0,2} and {1,3}; every edge crosses between the groups.
  • no edges
    in graph =
    out true
    With no edges there is nothing to violate the split — trivially bipartite.

Constraints

  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] does not contain u (no self-loops) and contains no duplicates.
  • The graph is undirected: if v is in graph[u], then u is in graph[v].
Saved
graph =
[[1,2,3],[0,2],[0,1,3],[0,2]]