FastPrep
Problem · Graph

Check Bipartite Graph

Learn this problem
● MediumInMobi logoInMobiNEW GRADOA

Problem statement

You are given a square binary matrix edges describing an undirected graph with vertices numbered from 0 through n - 1.

Vertices i and j are connected when edges[i][j] == 1 or edges[j][i] == 1. This convention allows an edge to be recorded in either half of the matrix.

Return true if the vertices can be divided into two groups such that every edge joins vertices from different groups. Otherwise, return false.

Function

isGraphBipartite(edges: int[][]) → boolean

Examples

Example 1

edges = [[0,1,0,0],[0,0,0,1],[0,0,0,0],[0,0,0,0]]return = true

The only edges are 0-1 and 1-3. One valid partition is {0, 3} and {1, 2}.

Example 2

edges = [[0,1,1],[0,0,1],[0,0,0]]return = false

Vertices 0, 1, and 2 form an odd cycle, so two groups are impossible.

Example 3

edges = [[0,1,0,1,0],[1,0,1,0,0],[0,1,0,1,0],[1,0,1,0,0],[0,0,0,0,0]]return = true

The four connected vertices form an even cycle, and vertex 4 is isolated. Every component is bipartite.

Constraints

  • 2 <= edges.length <= 300
  • edges[i].length == edges.length
  • edges[i][j] is either 0 or 1.
  • edges[i][i] == 0
  • An undirected edge is present when either edges[i][j] or edges[j][i] is 1.

More InMobi problems

drafts saved locally
public boolean isGraphBipartite(int[][] edges) {
    // write your code here.
}
edges[[0,1,0,0],[0,0,0,1],[0,0,0,0],[0,0,0,0]]
expectedtrue
checking account