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!!!!!!!
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!!!
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
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.
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
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 ?
i think another way to make the coding's easier is to set the visit value of a visited node as the previous node, that way you dont need to change the whole data type
This can be a solution public boolean isCycle(int V, ArrayList adj) { boolean[] visited = new boolean[V]; for (int i = 0; i < V; i++) { if (!visited[i] && checkCycle(i, adj, visited)) { return true; } } return false; } public boolean checkCycle(int start, ArrayList adj, boolean[] visited) { Queue queue = new LinkedList(); queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int top = queue.poll(); for (int v : adj.get(top)) { if (!visited[v]) { visited[v] = true; queue.add(v); } else if (v != top) { // If the adjacent node is visited and not the parent, it indicates a cycle. return true; } } } return false; }
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 🤷‼
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.
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)
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!
why not striver_69
Understood
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
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!!!!!!!
11:50 Wow the climax of the movie!! Amazing explanation striver. Thankyou :)
This is coder's gold mine. Thank you for such great explanations.
Thank you for this series and seriously this series is much much finer than the previous one!! Thank you.
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!!!
This Guy is like the greatest teacher for any student......Great Work Guruji 😉☺️
3 saal graph aadha adhura padha...ab raj baba ki kripa h ki roz ek video dekh ke confidence aa jata h XD
really great explanations covering all the edge cases and imp. small concepts in depth. You are really great bhaiya!
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Just came for revision , Man u r a legend So amazing explanation.
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.
Best explanation on Detecting Cycle Using BFS
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.
Understood! Awesome explanation as always, thank you so much!!
understood repeating is helpful and overall explanation is best that I could find in youtube
finally understood after 1 hour ..thanks
Understood, ea pura wow wala solution 😄.
Thankyou Striver, Understood!
Thanks! I was stuck at this problem for too long.
Understood, thanks!
Excellent Lecture bro ❤❤❤❤❤
Thank you So much Striver !
Awesome explanation man!! Keep doing the good work. Thanks
understood striver
great explanation
Awesome explanation bhaiya. You inspire us a lot. Hope to meet you someday.😇😇
Understood bhaiya!
Bhaiya your teaching style is awesome 🔥🔥🔥🔥🔥🔥🔥,
No Any youtuber can explain like u 😊😊
Extremely well as always
"UNDERSTOOD BHAIYA!!"
amazing intuition as always!!!tysm
Understood, Thank you so much.
really good explanation and visualization.
understood very well 💖
Great explanation
Understood.....🔥
Thankyou sir understood🙏❤🙇♂
god of coding for me
Understood striver ❤️
understood sir !
keep up the good work
Understood Sir!
Thank you sir
understood.. Thank you soo much
You are just amazing!!!, Plz keep uploading such a premium content.
understood very well
understood it very well
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
Noted ✌🏼
Thanks Striver
UNDERSTOOD:
Understood! 🙌
Outstanding..
Million Thanks
Understood ❤
Understood 👍
Thanks, understood
understood sir🙏
Understood 😇
Understood Bhaiya
understood thank you
thank you bhaiya
UnderStood❤
Understood💯💯💯
understood bhaiya
Understood.
Thanks a lot bhaiya
perfect
Added to notes
Understood sir
understood 😘😘
understood. PS: I guess there wasn't any need to pass V in bfs function
understood🧡🧡🧡
UNDERSTOOD
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 ?
tysm sir
understood!!
understooodddd
i think another way to make the coding's easier is to set the visit value of a visited node as the previous node, that way you dont need to change the whole data type
This can be a solution
public boolean isCycle(int V, ArrayList adj) {
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i] && checkCycle(i, adj, visited)) {
return true;
}
}
return false;
}
public boolean checkCycle(int start, ArrayList adj, boolean[] visited) {
Queue queue = new LinkedList();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int top = queue.poll();
for (int v : adj.get(top)) {
if (!visited[v]) {
visited[v] = true;
queue.add(v);
} else if (v != top) {
// If the adjacent node is visited and not the parent, it indicates a cycle.
return true;
}
}
}
return false;
}
@@adityavaste8963 this ones actually easier to grasp!
Understood!
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 🤷‼
understood!
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.
☑Understood
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.
understood.
Thank you very much. You are a genius.
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.
please make playlists for string as well
Understooood
Understood
Can you please tell till when will you upload all the remaining videos.
understood ,great explanation
as always LIT!
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. :)
Understood!!!! :D
Understood
11:57
🥶
Waiting for your surprise #independentWithStiver.
So am I
It’s delayed check linkedin