G-17. Bipartite Graph | BFS | C++ | Java
Vložit
- čas přidán 6. 09. 2024
- GfG-Problem Link: bit.ly/3SQQgId
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------
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😍😍😍
can you please tell me why my code is giving tle ??
bool check(vectorcolor , int start , vectoradj[]){
queueq;
q.push(start);
color[start] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
for(auto &i:adj[x]){
if(color[i] == -1){
color[i] = !color[x];
q.push(i);
}else if(color[i] == color[x]){
return false;
}
}
}
return true;
}
bool isBipartite(int V, vectoradj[]){
vectorcolor(V , -1);
for(int i = 0 ;i
congrats Brother :)💞
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🤣🤣🤣🤣
*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 !!
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.
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
Omg. Video at this time . Hats off to your
Work 👏👏
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
great explanation ... very easy to understand
true
really
yes ...
Bhai tu bhagwan h, mere liye, tujhe yaad karke, ek umeed jagti h, called "Let's try one more time", thanks buddy keep helping.
Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thanks bro, but in check function, you have to use call by reference(&) for array color to save the changes in other function.
Understood,sir.Very clear explanation.
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.
understood sir really nice explaination ............just simply brute force.........
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
u make every topic so easy... thanks a lot
Understood striver, thanks a lot!!
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😊
Understood! Super amazing explanation as always, thank you very much!!
Thank you very much.Yoy are a genius.
amazing explanation as always...
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)?
youre a geniuss striverr!!! tysm
understood ,as always great explanation
thanku so much for these quality
lectures
Understood thank you so so much.
Thank you sir 😊
Thank you very much. You are a genius.
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?
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
Wonderful explanation
understood to the core
using *_enums_* will make it much more intuitive.
understood striver
as always great explanation
understood
understood,great explanation
Understood, thanks!
Understood
Great explaination
understood completely
Thankyou sir understood🙇♂❤🙏
UNDERSTOOD!!!!!
Nice Explanation
Understood ❤
Missing your baap-beta concept bhaiya in this new graph series.Overall everything is really good.
I understood but there are flaws in the code u done ,but i understood the concept.
understood bhaiya!!
bhut acha padhate ho sir
UNDERSTOOD.
Thank you striver 😭😭
Thank you Bhaiya
understood, thanks a lot
So we have only 2 choice for the Colors?
For bi-partite, yes
Understood👍
understand thank you
understood bhaiya
thanks striver🙌
Understood!
Thank you 🙂
Understood💯💯💯
understood broskki !!
Understood 😃
Understood 😄😄
Code failing on larger testcases means component ka lafra
awesome
Always 💯💯💯💯💯
understood 🔥
yes
understood!!
Understood..
I was able to understand that odd length cycle will not be bipartite. Without any external help
Genius
gawwwwddddddddddd bhai 🙇♂🙇♂🙇♂🙇♂
understood!
Understood :)
understood💙💜💙
understood!!!!!!!!!!!
What is time complexity when graph have N node and N connected components
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
🔥🔥
Thank you, Striver 🙂
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.
What is the chromatic number of the graph, Is it somehow related to the coloring of the graph?
Where is the component logic video link ?
understood :-)
"understood"
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 !!
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
Understood
1st view💖
Op
US
ok
UnderStood
03:50 - Hey people, you watched 'Evil Dead Rise' movie?
can anybody send the correct code of this i am getting error at color
"UNDERSTAND"
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
US :) !!