Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

152. Is Graph Bipartite?

MediumDay 45 of 60Graphs

You are given an undirected graph with n nodes as an adjacency list: graph[u] lists the neighbours of node u. Return true if the nodes can be split into two groups so that every edge connects a node in one group to a node in the other group. The graph may be disconnected.

Example 1
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Nodes 0, 1 and 2 form a triangle, and an odd cycle can never be split into two sides.
Example 2
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Groups {0, 2} and {1, 3} work.
Constraints
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • graph[u] has no self loops or duplicates
  • If v is in graph[u], then u is in graph[v]
Hints
Frequently asked at: Meta, Amazon, Google
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min