Is Graph Bipartite
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
You're given an undirected network of nodes, where graph[u] lists every node directly connected to node u.
Determine whether you can split every node into exactly two opposing camps such that every connection in the network joins two nodes from different camps. No connection is ever allowed to join two nodes from the same camp.
Input: graph = [[1, 3], [0, 2], [1, 3], [0, 2]]
Output: True
Put nodes 0 and 2 in one camp and nodes 1 and 3 in the other. Every connection crosses between the two camps.
Input: graph = [[1, 2], [0, 2], [0, 1]]
Output: False
Every node here connects to both of the others. Whichever camp you place node 0 in, nodes 1 and 2 would need to be in the opposite camp from node 0, but they also connect to each other, so they'd need to be in opposite camps from one another too. That's impossible with only two camps.
Input: graph = [[1], [0], [3], [2]]
Output: True
This network has two separate pieces (0-1 and 2-3), and each piece on its own splits cleanly into two camps.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.