Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79
AMAAAZZZINNGGGG AS ALWAYYSSSS STRIVERRR!!! And for those who have difficulties in the LeetCode version, this is how it ran using my Java Code: class Solution { public boolean isBipartite(int[][] graph) { int n = graph.length; int[] colors = new int[n]; Arrays.fill(colors,-1); for(int i=0; i
*colour the src node as 0 *push src node into queue *check for adjacents : *if adjacent has not been coloured, colour it opposite to current node and push it into queue *else check if current node colour is same as adjacent node colour, if yes return false
Striver I grinded DSA in the last few months, referred to your videos whenever in doubt. I just got my internship in a really good company ! Much love ❤️
Equivalent definitions of a bipartite graph: 1)There is no cycle of odd length 2)A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.(leetcode description) 3).The graph should be bi-colourable.
Understood bhaiyya, I was able to solve this problem by myself, it is quite similar to finding a cycle in a graph, just a few changes in the code. Thankyou so much
He already made videos on how to detect a cycle by using both bfs and dfs.. We can keep count variable to keep track of length i guess.. Try it out once it will be super excited experience.
@@aeroabrar_31 you cannot directly use a counter to track the length, as in the methods discussed, we just check if the adj is already visited or not. What if the graph has a cycle somewhere in between? How would you use the above methods to find the starting point of a cycle(from where the counting should be done)?
it's the same thing like adjacency list, just the index represents the u and its components as v. Like, graph = [[1,2,3],[0,2],[0,1,3],[0,2]] means 0 : {1,2,3} 1 : {0,2} 2 : {0,1,3} 3 : {0,2} my code for this problem is as : bool bfs(int i, vector& graph, vector& col) { queueq; q.push({i,1}); col[i] = 1; while(!q.empty()){ pairp = q.front(); q.pop(); for(auto it: graph[p.first]){ if(col[it]==-1){ col[it] = !p.second; q.push({it,col[it]}); } else if(col[it]==p.second){ return false; } } } return true; }
bool isBipartite(vector& graph) { int n = graph.size(); vector col(n,-1); for(int i=0;i
The only thing I am not getting is why we are doing BFS for every node in graph if it's not colored before? Is this because the graph can be in the form of connected components? Why cant we do the way we did for finding cycle, add the root node and then keep going from there.
Python solution (BFS): from collections import deque class Solution: def isBipartite(self, V, adj): #code here def bfs(src, vis): vis[src] = "0" q = deque() q.append(src) while q: node = q.popleft() for adjNode in adj[node]: if vis[adjNode] == -1: vis[adjNode] = "0" if vis[node] == "1" else "1" q.append(adjNode) elif vis[adjNode] == vis[node]: return False return True vis = [-1]*V for i in range(V): if vis[i] == -1: if not bfs(i, vis): return False return True
I was using nearly same code, but using 0s and 1s instead of strings of 0s and 1s but it was not working, I copied striver's code but still it was not working, can you tell if using strings helps or just my code was trash: Here is my code: from collections import deque class Solution: def check(self, start, adj, V, colored): q = deque() q.append(start) colored[start] = 0 while q: node = q.popleft() for i in adj[node]: if colored[i]==-1: colored[i]=(~(colored[node])) q.append(i) elif colored[i]==colored[node]: return False
return True
def isBipartite(self, V, adj): colored = [-1 for i in range(V)] for i in range(V): if colored[i]==-1: if self.check(i, adj, V, colored)==False: return False return True
#include #include using namespace std; class Solution { public: bool isBipartite(vector& graph) { int n = graph.size(); vector col(n, 0); // 0 - unvisited, 1 - color 1, 2 - color 2 queue q;
for (int i = 0; i < n; i++) { if (col[i] == 0) { // Not visited q.push(i); col[i] = 1; // Start coloring the first node with color 1
while (!q.empty()) { int t = q.front(); q.pop(); int validcol = (col[t] == 1) ? 2 : 1; // Toggle color
for (int neighbor : graph[t]) { if (col[neighbor] == 0) { // Not visited col[neighbor] = validcol; // Color with valid color q.push(neighbor); } else if (col[neighbor] == col[t]) { // Same color as current node return false; // Not bipartite } } } } }
return true; // All components are bipartite } };correct sol
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
just want to thanks bhai, yesterday i got selected in 14 lpa package, you will always be one of the major reasons for my selection.
As a fresher?
@@aniruddhadas1778 Yeah
congratulations bro😍😍😍
congrats Brother :)💞
Congrats bro and wanted to ask, ig package is 14 or CTC is 14?
AMAAAZZZINNGGGG AS ALWAYYSSSS STRIVERRR!!!
And for those who have difficulties in the LeetCode version, this is how it ran using my Java Code:
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] colors = new int[n];
Arrays.fill(colors,-1);
for(int i=0; i
*colour the src node as 0
*push src node into queue
*check for adjacents :
*if adjacent has not been coloured, colour it opposite to current node and push it into queue
*else check if current node colour is same as adjacent node colour, if yes return false
Thanks !!
Striver I grinded DSA in the last few months, referred to your videos whenever in doubt. I just got my internship in a really good company ! Much love ❤️
How ....? can you help me !
@@successsavataar.ai786 me too
codesoft🤣🤣🤣🤣
Omg. Video at this time . Hats off to your
Work 👏👏
Equivalent definitions of a bipartite graph:
1)There is no cycle of odd length
2)A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.(leetcode description)
3).The graph should be bi-colourable.
Space = O(n) + O(n)
Time = O(n) * [O(n)+O(2E)]
Time complexity is wrong
It will be O(n) + O(n + 2E) as you are not doing full bfs each time in the outer loop
Bhai tu bhagwan h, mere liye, tujhe yaad karke, ek umeed jagti h, called "Let's try one more time", thanks buddy keep helping.
Understood,sir.Very clear explanation.
Understood bhaiyya, I was able to solve this problem by myself, it is quite similar to finding a cycle in a graph, just a few changes in the code. Thankyou so much
understood sir really nice explaination ............just simply brute force.........
Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood! Super amazing explanation as always, thank you very much!!
u make every topic so easy... thanks a lot
Hey striver! This is a very cool series to revise your concepts. Here you missed a case where there's a self loop at a node.
youre a geniuss striverr!!! tysm
understood ,as always great explanation
Thanks bro, but in check function, you have to use call by reference(&) for array color to save the changes in other function.
Understood. The previous correction I did was silly. It was correct.
Loving the graph series bhaiya ❤❤
Thank you for this series ❤🙏
Able to solve it on my own all thnks to u😊
25 din baad placement start ho rhe h mere yha pr aur kya hi kismat h bhai.
did you got any offer ?
placement kaisa hua?
offer mila kya?
understood striver
as always great explanation
thanku so much for these quality
lectures
amazing explanation as always...
Understood striver, thanks a lot!!
Thank you very much.Yoy are a genius.
Thank you very much. You are a genius.
Is there any way to detect cycle in a graph and find if its odd length or even ?
-> then we will return true if even , and false if odd
He already made videos on how to detect a cycle by using both bfs and dfs..
We can keep count variable to keep track of length i guess..
Try it out once it will be super excited experience.
@@aeroabrar_31 you cannot directly use a counter to track the length, as in the methods discussed, we just check if the adj is already visited or not. What if the graph has a cycle somewhere in between? How would you use the above methods to find the starting point of a cycle(from where the counting should be done)?
Wonderful explanation
great explanation ... very easy to understand
true
really
yes ...
bhut acha padhate ho sir
understood,great explanation
Missing your baap-beta concept bhaiya in this new graph series.Overall everything is really good.
Thankyou sir understood🙇♂❤🙏
I understood but there are flaws in the code u done ,but i understood the concept.
understood bhaiya!!
understood to the core
using *_enums_* will make it much more intuitive.
Thank you striver 😭😭
can we initialize the element in the color array by int color[V] = {-1}; instead of looping over the entire array and changing index by index?
use vector and pass -1 in constructor or use memset for arrays
Understood thank you so so much.
Thank you sir 😊
Nice Explanation
Great explaination
UNDERSTOOD!!!!!
Understood, thanks!
Understood 😄😄
understood completely
03:50 - Hey people, you watched 'Evil Dead Rise' movie?
understood broskki !!
Understood❤
thanks striver🙌
What is time complexity when graph have N node and N connected components
Understood💯💯💯
What is the chromatic number of the graph, Is it somehow related to the coloring of the graph?
Understood👍
So we have only 2 choice for the Colors?
For bi-partite, yes
hey, in 785 ques leetcode, what is the given parameter "graph" is?? its weird some set thing is going on
its given in matrix form not in list.... but if u will go on gfg u will find the same question in list form
as striver solved in the video
it's the same thing like adjacency list, just the index represents the u and its components as v. Like,
graph = [[1,2,3],[0,2],[0,1,3],[0,2]] means
0 : {1,2,3}
1 : {0,2}
2 : {0,1,3}
3 : {0,2}
my code for this problem is as :
bool bfs(int i, vector& graph, vector& col) {
queueq;
q.push({i,1});
col[i] = 1;
while(!q.empty()){
pairp = q.front();
q.pop();
for(auto it: graph[p.first]){
if(col[it]==-1){
col[it] = !p.second;
q.push({it,col[it]});
}
else if(col[it]==p.second){
return false;
}
}
}
return true;
}
bool isBipartite(vector& graph) {
int n = graph.size();
vector col(n,-1);
for(int i=0;i
@@krishgupta4408 thankyou!!
@@deviprasad_bal thankyou so much!!
@@deviprasad_bal thanks man !!
I was able to understand that odd length cycle will not be bipartite. Without any external help
Genius
gawwwwddddddddddd bhai 🙇♂🙇♂🙇♂🙇♂
The only thing I am not getting is why we are doing BFS for every node in graph if it's not colored before? Is this because the graph can be in the form of connected components? Why cant we do the way we did for finding cycle, add the root node and then keep going from there.
Graph can have connected components in it. For reference you can look into LC question which is much more detailed than GFG.
class Solution {
private:
bool check(int start, int V, vectoradj[], int color[]){
queue q;
q.push(start);
color[start] = 0;
while(!q.empty()){
int node = q.front();
q.pop();
for(auto &it: adj[node]){
if(color[it] == -1){
color[it] = !color[node];
q.push(it);
}
else {
if(color[it] == color[node]){
return false;
}
}
}
}
return true;
}
public:
bool isBipartite(int V, vectoradj[]){
int color[V]; //0 or 1
for(int i=0; i
Understood😃
Code failing on larger testcases means component ka lafra
understood bhaiya
understood, thanks a lot
Thank you Bhaiya
UNDERSTOOD.
Thank you 🙂
Where is the component logic video link ?
Understood :)
Dec'25, 2024 09:03 pm
understood 🔥
Always 💯💯💯💯💯
here why we can't use
int colour[V] = {-1}; ??
Thank you, Striver 🙂
understood💙💜💙
Python solution (BFS):
from collections import deque
class Solution:
def isBipartite(self, V, adj):
#code here
def bfs(src, vis):
vis[src] = "0"
q = deque()
q.append(src)
while q:
node = q.popleft()
for adjNode in adj[node]:
if vis[adjNode] == -1:
vis[adjNode] = "0" if vis[node] == "1" else "1"
q.append(adjNode)
elif vis[adjNode] == vis[node]:
return False
return True
vis = [-1]*V
for i in range(V):
if vis[i] == -1:
if not bfs(i, vis): return False
return True
I was using nearly same code, but using 0s and 1s instead of strings of 0s and 1s but it was not working, I copied striver's code but still it was not working, can you tell if using strings helps or just my code was trash:
Here is my code:
from collections import deque
class Solution:
def check(self, start, adj, V, colored):
q = deque()
q.append(start)
colored[start] = 0
while q:
node = q.popleft()
for i in adj[node]:
if colored[i]==-1:
colored[i]=(~(colored[node]))
q.append(i)
elif colored[i]==colored[node]:
return False
return True
def isBipartite(self, V, adj):
colored = [-1 for i in range(V)]
for i in range(V):
if colored[i]==-1:
if self.check(i, adj, V, colored)==False:
return False
return True
UNDERSTOOD;
Understood!
Understood :)
Striver bro can you please share your timings you follow .at 3.30 u r uploading u r video,why do u sleep brother ?🤔
He is in Warsaw
Beware in using vis/color vector...
Sep'5, 2923 11:41 pm
understand thank you
can anybody send the correct code of this i am getting error at color
Understood
understood!!
thank you
understood!
understood!!!!!!!!!!!
i guess the same solution in Leetcode is giving TLE.....
#include
#include
using namespace std;
class Solution {
public:
bool isBipartite(vector& graph) {
int n = graph.size();
vector col(n, 0); // 0 - unvisited, 1 - color 1, 2 - color 2
queue q;
for (int i = 0; i < n; i++) {
if (col[i] == 0) { // Not visited
q.push(i);
col[i] = 1; // Start coloring the first node with color 1
while (!q.empty()) {
int t = q.front();
q.pop();
int validcol = (col[t] == 1) ? 2 : 1; // Toggle color
for (int neighbor : graph[t]) {
if (col[neighbor] == 0) { // Not visited
col[neighbor] = validcol; // Color with valid color
q.push(neighbor);
} else if (col[neighbor] == col[t]) { // Same color as current node
return false; // Not bipartite
}
}
}
}
}
return true; // All components are bipartite
}
};correct sol
🔥🔥
Understood..
thanks!
awesome
understood
1st view💖
understood :-)
UnderStood
yes
"UNDERSTAND"