Is Graph Bipartite? - Leetcode 785 - Python
Vložit
- čas přidán 23. 07. 2024
- Solving Is Graph Bipartite? - Leetcode 785, today's daily leetcode problem on may 18.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/minimum...
0:00 - Read the problem
0:30 - Drawing Explanation
5:50 - Coding Explanation
leetcode 785
#neetcode #leetcode #python
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
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.
How does the code account for the disconnected vertex of the graph?
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: czcams.com/video/69rcy6lb-HQ/video.html
That was fast. Keep it up!
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!
The problem's description made no sense to me, your explanation was very helpful.
in line 17 when you say odd[nei] = -1 * odd[i], can we equivalently say odd[nei] = not odd[i] ?
tbh odd even made it more difficult to understand
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
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
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?
I wish some day I will resolve such problems on my own.
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
can we use Defaultdict ?
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
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.
Thank you.
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.
Just a correction, the problem link given is for 1557 and not for 785 :)
tough Q if you've never seen it before
I just don't understand the meaning of bipartite but now I do
once I realized what is bipartite graph, it became soooo much simpler >_
oh so its basically an N colouring problem
No offence but i feel like you beat around the bush a lot without really telling what is the intuition behind the solution
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