Is Graph Bipartite? - Leetcode 785 - Python

Solving Is Graph Bipartite? - Leetcode 785, today's daily leetcode problem on may 18.

0:00 - Read the problem
0:30 - Drawing Explanation
5:50 - Coding Explanation

leetcode 785

#neetcode #leetcode #python

[sanjeevrajora]

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

[sergiofranklin]

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

[uptwist]

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();
};

[ningzedai]

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

[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!

[krishnachoudhary]

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.

[nizarkadri]

tbh odd even made it more difficult to understand

[neerajvshah]

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

[VladiqLot]

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

[sumitsharma]

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

[janambagdai]

Firstly, the video is amazing, thanks for that. However, I got confused by the word "visited". Here, we are using the odd array to actually mark the vertex, and not explore it. If it has been already marked before, we pass. Correct me if I am wrong?

[edmonddantes]

tough Q if you've never seen it before

[YT.Nikolay]

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

[aditya-lrin]

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

[CS_nb]

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?

[julianelmasry]

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

[shrutiverma]

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.

[ren]

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

[gnes]

oh so its basically an N colouring problem

[joelgantony]

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