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
@@aeroabrar_31 No I think if he started using horizontal data structure we will get confused because we are used to drawing it out like that from all previous lectures and series!
We can also solve it without storing the parent , A particular node can be marked visited only by its parent so when we reach a node and traverse all its adjacent node and find more than one visited ,that shows this node has more than one parent or we can simply say this particular node is also getting visited from another direction and in that case we can say there is cycle presert . class Solution { public: // Function to detect cycle in an undirected graph. bool bfs(int node,vector &vis, vector adj[]){ queue q; q.push(node); vis[node]=1; while(!q.empty()){ int frnt= q.front(); q.pop(); int cnt=0; for(auto it:adj[frnt]){ if(!vis[it]){ q.push(it); vis[it]=1; } else { cnt++; } } if(cnt>1) return true; } return false; } bool isCycle(int V, vector adj[]) { // Code here vector vis(V,0); for(int i=0;i
I still don't get it how. How will you know parent is visiting that node. If graph is like 1 then 2 3 and then 4 5 connected respectively then if we are at 4 then 2 is already visited. and then it will go in else case will do ++ and after that return true
@@gautamgupta7148 can't explain properly here.... But while iterating in the adj list... If there are more than two visited nodes, then it will have cycle..... This is same concept as described by the guy above
I look at the comments in LeetCode's Discussion tab when they talk about DP and I go like: why the hell is everybody scared of DP. It's not that hard. ONLY HAPPENS WHEN YOU LEARN FROM STRIVERRR1!!!!!!!
Hey Striver, amazing video, there's one suggestion: You don't need to loop once in boolean array, as in Java the values are false by default, same for int[] array its filled with 0 initially, Well, in DP I use Arrays.fill(arr, -1); //Internally this method runs a loop and saves much code space. Edit: we can also use if( !vis[i] ) //this will check if it is false or not, to check if the node is already visited or not! Love your videos! Thanks
11:52 Bro! It seems like someone stole ur child! LOLLLL!! Only Striver can have that much fun and enthusiasm in a lesson!! Thank youuu sir for making us smile and learn at the same time!!!
If for a node, any 2 connected nodes are already visited then we can say it is cycle. Because one of them will be parent and other one is already visited by some other node. For example, 2->3,4,5 Let say 3 and 4 already visited then one of them must be parent and other one is visited by some other node. In that way we xan avoid to store the parent info in the queue.
Hi Striver, Great explanation. I have one query and i.e. To solve any problem if we are using queue, in that case do we need to use queue with array or queue with linked list? Specially when programming with javascript. Thanks.
Thanks for the lecture. Just a quick question, if there is a time limitation, is there any difference if I just do the older graph series? What would you recommend? ( I have only 1-2 weeks remaining)
hiii.. will this logic still work if there are only 2 nodes in the graph and a cycle exists between them such that 0->1 and 1->0? because in that case the iterator will always be equals to parent??
This is an undirected graph thus the condition u mentioned will always be true for all the edges . Hence we have to detect the cycle in the graph as a whole with undirected edges which will always be formed with 3 or more edges.
Doubt in TC: We are not multiplying and are only adding the TC O(V) for looping on the visited vector , reason given by striver for that is because we are not going to call that for each node as most nodes will be visited when starting from a node , but my doubt is still hum call toh number of nodes ke liye hi krenge na vis vector vale loop mein voh alag baat h ki dfs() function call kis kis ke liye hoga 🤷‼
1- remove from the graph the nodes that have less than 2 connections 2- count the connections 3- count the nodes 4 - if the connections are equals or more than the nodes you have a cycle how is this method called?🙃
bhya , @8:25 , u said someone at the same level shd have touched it, bcoz it's an even cycle, but if it's an odd length cycle, someone at same or a prior level should have touched it, would follow right? m confiused at that.. @take U forward ?
what if instead of using a parent variable we use a map to check all the current elemets present in the queue and if the element is visited and also present in the map then it cannot be parent so must be a cycle
you are just amazing bro i had watched babbar DSA 90 videos i do tell you that you have very nice skill of teaching i am not comparing but ya you are like suryakumar yadav kam me jyada ka maja to the point straight to the concept
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
@takeUforward
Please use Queue as a horizontal data structure , being confused as like stack..
understood
@@aeroabrar_31 No I think if he started using horizontal data structure we will get confused because we are used to drawing it out like that from all previous lectures and series!
We can also solve it without storing the parent , A particular node can be marked visited only by its parent so when we reach a node and traverse all its adjacent node and find more than one visited ,that shows this node has more than one parent or we can simply say this particular node is also getting visited from another direction and in that case we can say there is cycle presert .
class Solution {
public:
// Function to detect cycle in an undirected graph.
bool bfs(int node,vector &vis, vector adj[]){
queue q;
q.push(node);
vis[node]=1;
while(!q.empty()){
int frnt= q.front();
q.pop();
int cnt=0;
for(auto it:adj[frnt]){
if(!vis[it]){
q.push(it);
vis[it]=1;
}
else {
cnt++;
}
}
if(cnt>1) return true;
}
return false;
}
bool isCycle(int V, vector adj[]) {
// Code here
vector vis(V,0);
for(int i=0;i
Nice Idea: since there can only be one parent. If 'else' part runs more than once, it means there is a cycle.
thanks for sharing this alternative, its always good to know more than one way to solve a problem.
nice
I still don't get it how. How will you know parent is visiting that node. If graph is like 1 then 2 3 and then 4 5 connected respectively then if we are at 4 then 2 is already visited. and then it will go in else case will do ++ and after that return true
@@gautamgupta7148 can't explain properly here.... But while iterating in the adj list... If there are more than two visited nodes, then it will have cycle..... This is same concept as described by the guy above
Thank you for this series and seriously this series is much much finer than the previous one!! Thank you.
People told me that graph is a hard topic and many people failed to do so, but Striver's Graph series is just Amazing it looks quite easy for me. ♥
I look at the comments in LeetCode's Discussion tab when they talk about DP and I go like: why the hell is everybody scared of DP. It's not that hard.
ONLY HAPPENS WHEN YOU LEARN FROM STRIVERRR1!!!!!!!
Hey Striver, amazing video, there's one suggestion: You don't need to loop once in boolean array, as in Java the values are false by default, same for int[] array its filled with 0 initially,
Well, in DP I use Arrays.fill(arr, -1); //Internally this method runs a loop and saves much code space.
Edit: we can also use if( !vis[i] ) //this will check if it is false or not, to check if the node is already visited or not!
Love your videos! Thanks
Thanks, I was googling and writing java code. Will keep this in mind.
This is coder's gold mine. Thank you for such great explanations.
This Guy is like the greatest teacher for any student......Great Work Guruji 😉☺️
11:50 Wow the climax of the movie!! Amazing explanation striver. Thankyou :)
really great explanations covering all the edge cases and imp. small concepts in depth. You are really great bhaiya!
Just came for revision , Man u r a legend So amazing explanation.
3 saal graph aadha adhura padha...ab raj baba ki kripa h ki roz ek video dekh ke confidence aa jata h XD
11:52 Bro! It seems like someone stole ur child! LOLLLL!! Only Striver can have that much fun and enthusiasm in a lesson!! Thank youuu sir for making us smile and learn at the same time!!!
If for a node, any 2 connected nodes are already visited then we can say it is cycle. Because one of them will be parent and other one is already visited by some other node.
For example, 2->3,4,5
Let say 3 and 4 already visited then one of them must be parent and other one is visited by some other node.
In that way we xan avoid to store the parent info in the queue.
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood! Awesome explanation as always, thank you so much!!
Best explanation on Detecting Cycle Using BFS
Thankyou Striver, Understood!
Bhaiya your teaching style is awesome 🔥🔥🔥🔥🔥🔥🔥,
No Any youtuber can explain like u 😊😊
Awesome explanation bhaiya. You inspire us a lot. Hope to meet you someday.😇😇
Understood, ea pura wow wala solution 😄.
Understood, thanks!
Hi Striver, Great explanation. I have one query and i.e. To solve any problem if we are using queue, in that case do we need to use queue with array or queue with linked list? Specially when programming with javascript. Thanks.
Thanks! I was stuck at this problem for too long.
Thanks for the lecture. Just a quick question, if there is a time limitation, is there any difference if I just do the older graph series? What would you recommend? ( I have only 1-2 weeks remaining)
Yes you can, just check the problems that I add here
@@takeUforward thanks a lot for the quick response!
understood repeating is helpful and overall explanation is best that I could find in youtube
Understood bhaiya!
hiii.. will this logic still work if there are only 2 nodes in the graph and a cycle exists between them such that 0->1 and 1->0? because in that case the iterator will always be equals to parent??
I too have the same doubt! please comment if you get the answer elsewhere.
This is an undirected graph thus the condition u mentioned will always be true for all the edges . Hence we have to detect the cycle in the graph as a whole with undirected edges which will always be formed with 3 or more edges.
Alright thank you
i guess that cannot be considered as a cycle.
amazing intuition as always!!!tysm
keep up the good work
Excellent Lecture bro ❤❤❤❤❤
really good explanation and visualization.
"UNDERSTOOD BHAIYA!!"
Understood, Thank you so much.
Doubt in TC:
We are not multiplying and are only adding the TC O(V) for looping on the visited vector , reason given by striver for that is because
we are not going to call that for each node as most nodes will be visited when starting from a node , but my doubt is still hum call toh number of
nodes ke liye hi krenge na vis vector vale loop mein voh alag baat h ki dfs() function call kis kis ke liye hoga 🤷‼
Extremely well as always
very well
understood
Understood ❤❤❤
1- remove from the graph the nodes that have less than 2 connections
2- count the connections
3- count the nodes
4 - if the connections are equals or more than the nodes you have a cycle
how is this method called?🙃
Understood.....🔥
understood striver
great explanation
Awesome explanation
understood
understood. PS: I guess there wasn't any need to pass V in bfs function
Understood
Can you please tell till when will you upload all the remaining videos.
Understood!!!! :D
Understood 😊
understood.. Thank you soo much
bhya , @8:25 , u said someone at the same level shd have touched it, bcoz it's an even cycle, but if it's an odd length cycle, someone at same or a prior level should have touched it, would follow right? m confiused at that.. @take U forward ?
Sir, why the visited array is not passed by reference in the function?
because array is already passed by reference .
bhai gusse me bhi arre the lagra beech beech me
understood very well 💖
understood sir !
Thank you sir
Understood! 🙌
Thankyou sir understood🙏❤🙇♂
Outstanding..
as always LIT!
Hi, Why are you making another video on the same topic that you already covered 1 year ago, which one should we choose to watch?
Am I the only one who doesn't understand why he uses the + sign instead of the * sign in time complexity?? Please help if you understand!
Yes I think you're the only one.
understood it very well
what if instead of using a parent variable we use a map to check all the current elemets present in the queue and if the element is visited and also present in the map then it cannot be parent so must be a cycle
can u elaborate?
12:01 can anyone please help me with that logic?
I dont get what he is trying to say there
Well, Parent here means the previous node. And suppose, if next node is already visited but it is not previous node then it means, cycle exist.
You are just amazing!!!, Plz keep uploading such a premium content.
you are just amazing bro i had watched babbar DSA 90 videos i do tell you that you have very nice skill of teaching i am not comparing but ya you are like
suryakumar yadav
kam me jyada ka maja
to the point straight to the concept
can someone tell me why the visited array is not being passed as reference ?
Because in c++ arrays are already passed as reference you don't need to write &
understood!
understooodddd
please make playlists for string as well
Thanks Striver
perfect
Thanks, understood
Understood
Understood Sir!
Understood striver ❤️
god of coding for me
Noted ✌🏼
understood thank you
11:57
🥶
Bro what is the difference between if(adjacentNode != parent) and if(parent != adjacentNode) Plz tell 🙏🙏
It's the same.
seriously?
@@codingalley6229 he might be a beginner, you need to chill
Million Thanks
Bhaiya, why is the clarity so less?? while writing code in gfg??
Understood 😃
tysm sir
What is the use of parent array here
Thanks a lot bhaiya
which whiteboard u are using?
Why not dfs??
am i the only one who isn't able to understand the formate in which input are supplied in the question?
does self cycle exist in this graph?
understood sir🙏
Waiting for your surprise #independentWithStiver.
So am I
It’s delayed check linkedin
Understood!
thank you bhaiya
Understood Bhaiya
Understood💯💯💯
Potential Mistake: Ugnoring to consider there may be more than one disjoint set in the graph
Sep'5, 2023 10:34 pm
Understood.
understood bhaiya
understood!!
Understood. :)