Is Graph Bipartite? - Leetcode 785 - Python

[@sergiofranklin8809]

may be this one would be easier to understand:
def isBipartite(self, graph: List[List[int]]) -> bool:
color = {}
for node in range(len(graph)):
if node not in color:
color[node] = 0
q = deque([node]) #bfs starts here
while q:
node = q.popleft()
for nei in graph[node]:
if color[nei] == color[node]: #if neighbours have same color then return False
return False
if nei not in color:
q.append(nei)
color[nei] = color[node] ^ 1 #just sets opposite number/color to neighbour
return True

[@amanbaghel1104]

can we use Defaultdict ?

[@chengyuan455]

In this line " if color[nei] == color[node]: #if neighbours have same color then return False" you have to check also if nei is in color, otherwise can cause key error

[@chengyuan455]

I don't know if they added new test cases, but for some reason when I run the code in video, which I double checked no typo or differences, only 76/81 test cases were passed. However, your code worked like charm after tweaking the line I mentioned.

[@nizarkadri3109]

tbh odd even made it more difficult to understand

[@BananaButcher]

lol i was thinking the same. idk why he is making this classic problem more difficult

[@sanjeevrajora7335]

Today's question was just so awfully explained on leetcode but you explain it so well that i can able to do it of my own.Thank you

[@uptwist2260]

Thanks again for the daily. I was scared from the problem description and once I watched your breakdown at the beginning, I got it.
Here is my JS Solution:
var isBipartite = function(graph) {
let bfsSolution = function() {
let visited = new Array(graph.length); // unvisited == undefined; set1 == true; set2 == false

let bfs = function(root) {
let dequeue = [root];
while (dequeue.length > 0) {
let node = dequeue.shift();
for (let neighbor of graph[node]) {
if (visited[neighbor] === undefined) {
dequeue.push(neighbor);
visited[neighbor] = !visited[node];
} else if (visited[node] == visited[neighbor]) {
return false;
}
}
}
return true;
}

for (let node = 0; node < graph.length; node += 1) {
visited[node] = visited[node] ?? false;
if (bfs(node) === false) return false;
}

return true;
}

return bfsSolution();
};
This problem reminded me of 1129. shortest path with alternating colors, but the pattern really was not similar lol, in retrospect. The word alternating just stuck with me... Here it is: th-cam.com/video/69rcy6lb-HQ/w-d-xo.html

[@ningzedai9052]

This problem can be solved by UnionFind as well, which is easier to understand. The nodes in each array should be sharing the same parent, while the index of that array should have a different parent. Based on this condition, we can return the result.
def isBipartite(self, graph: List[List[int]]) -> bool:
n = len(graph)
uf = UF(n)
for u in range(n):
pu = uf.find(u)
lu = len(graph[u])
if lu == 1:
pv = uf.find(graph[u][0])
if pu == pv:
return False
elif lu > 1:
for i in range(len(graph[u]) - 1):
first, second = graph[u][i], graph[u][i + 1]
uf.union(first, second)
pf, ps = uf.find(first), uf.find(second)
if pu == pf or pu == ps:
return False
return True

[@TheManTheMythThe]

Gave it some thought and I think the for loop can be shortened to something like below
for node, neighbors in enumerate(graph):
node_parent = uf.find(node)
for neighbor in neighbors:
if node_parent == uf.find(neighbor):
return False
for next_neighbor in neighbors[1:]:
uf.union(neighbors[0], next_neighbor)
return True

[@krishnachoudhary4924]

Amazing. I really like your fast review feature in your website, one small request would be to please add problem link after the video solution. Thanks once again for amazing explanation.

[@StanisLoveSid]

Hi Neetcode, thank you so much for your videos! In your last episodes you're really quick, could you please slow a little bit down next time? I just can't catch information sometimes, hope I'm not the only one with this problem. Thank you one more time!

[@VladiqLot]

I wish some day I will resolve such problems on my own.

[@neerajvshah]

The problem's description made no sense to me, your explanation was very helpful.

[@edmonddantes587]

tough Q if you've never seen it before

[@Bukalemur]

That was fast. Keep it up!

[@aditya-lr2in]

Just a correction, the problem link given is for 1557 and not for 785 :)

[@YT.Nikolay]

once I realized what is bipartite graph, it became soooo much simpler >_

[@mohamednegm8550]

Union find

[@CS_n00b]

I dont get 'if odd[nei] and odd[i] == odd[nei]:'. If we are starting the bfs from a different part of the graph at 'even' and reach another point that was searched before, if it was even for the old search but odd for the new search I dont see why this is False? We could just be lagged by a few odd number of moves in the new search?

[@sumitsharma6738]

I just don't understand the meaning of bipartite but now I do

[@gnes04]

oh so its basically an N colouring problem

[@MP-ny3ep]

Thank you.

[@julianelmasry9556]

in line 17 when you say odd[nei] = -1 * odd[i], can we equivalently say odd[nei] = not odd[i] ?

[@shrutiverma2594]

There's a bug. BFS is confusing you are giving i to both starting variable and popped one from queue it is slightly confusing which i it is.

[@ren5124]

How does the code account for the disconnected vertex of the graph?

[@joelgantony]

No offence but i feel like you beat around the bush a lot without really telling what is the intuition behind the solution

[@sumitsharma6738]

class Solution {
public boolean isBipartite(int[][] graph) {
HashSet s1 = new HashSet();
HashSet s2 = new HashSet();
boolean[] isVisited = new boolean[graph.length];
for(int i=0;i