DIY: Is Graph Bipartite?

Solve the interview question "Is Graph Bipartite?" in this lesson.

We'll cover the following

Problem statement

In this challenge, you will be given an undirected graph. Your task is to determine if this graph is bipartite or not.

A graph is bipartite if we can split its set of nodes into two independent subsets, A and B, such that every edge in the graph has one node in A and another node in B.

Input

An undirected graph is given as input. This graph will be represented by a 2D array such that graph[i] will contain a list of indices j for which the edge between nodes i and j exists. Each node in the graph is denoted by integers from 0 to len(graph)-1.

For example, the input can be:

graph = [[1], [0, 3], [3], [1, 2]]

This graph can be illustrated as:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.