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
Amazing explanation bhaiya really amazing. Was trying to understand it from many source but was not able to understand properly. Really enjoy your teaching. Keep going bhaiya
Understanding more and more each day that I'm not smart enough to understand this high level logic Spent 1 year to understand, still haven't understood anything
Can anyone tell me that why striver has used a vector of array for the visited array instead of a single vector/array in C++ code, or its just mistyped while coding ??
Instead of "if(dfs(adjacentNode, node, visited, adj) == true) return true; ", if we directly return the dfs function, then it is incorrect. Whu so ? I think It should be same
Because detect function will return true or false for every component between one to n, Lets say first component has no cycle, but second one has a cycle. But according to your code, it will not go to second component, it will just return false after iterating in first component. So, if detect function sends a true, then only you should return true, else nothing
the concept of more than two parent to detect cycle is also good...... If in any adjacency list, if we find two or more visited node during BFS or DFS in a undirected graph then it will have a cycle. bool detectcycle(int i, vector&vis, vectoradj[]){ bool iscycledetected=false; vis[i]=1; int count=0; for(auto K:adj[i]){ if(vis[K])count++; } if(count>1)iscycledetected=true;// this is the check for cycle
Hey Striver, I had a doubt, why do we need to store the parent of each node? Can't we just count the number of neighboring nodes, of a particular node, that are visited, if the count is more than 1, for any node, then we can conclude that the cycle is present? Plz let me know if I am missing out on something in my approach. Following is the implementation for the above logic: bool detectDfs(int start, vector adj[], int vis[]){ vis[start] = 1; int visCnt = 0; bool flag = false; for(auto it : adj[start]){ if(++visCnt > 1) flag = true; else if(!vis[it]){ flag = flag || detectDfs(it, adj, vis); } if(flag == true) return flag; } return flag; } bool isCycle(int V, vector adj[]) { // Code here int vis[V] = {0}; for(int i = 0; i < V; i++){ if(!vis[i] && detectDfs(i, adj, vis)) return true; } return false; }
@@kanishkraj5640 I understood @Aniket 's qn but couldn't understand your answer. How can a node be visited, not be the parent, and yet no cycle is formed?
In this example you can visit back to the parent node if not stored them. 1 ( 2 3) 2 (1 3) Here you will go to 2 from 1 and again 1 from 2 and you got your cycle when there is no cycle at all.
No, if u have a graph with one node and 3 outwards edge , then it doesnt mean its a cycle right? like 1--->2,3,4 so u visit 2,3 from 1 and visit counts become 2 > 1 , does that mean it has a cycle? No
you dont want that function to be exposed somewhere else! you specifically want dfs or dfs for this solution class only and other classes if made can have their methods likewise. yes u can add the function under public too not an issue but as far as clean code is concerned its better to add under private "Methods that serve as the inner workings of your class and don’t output or display information." read this carefully for private
A simple question if anyone can help me understand! If we are given a source node and we are performing DFS on a connected undirected graph(i.e. a single component), how is the time complexity O(N+2E), shoudn't it be just O(2E) which is summation of degrees?
can someone please help me to find out why this code is not working.. class Pair{ int first,second; public Pair(int first,int second){ this.first=first; this.second=second; } } class Solution { boolean dfscdetect(int node,int parent,ArrayList adj,int vis[]){ vis[node]=1; for(int nbs:adj.get(node)){ if(vis[nbs]==0){ return dfscdetect(nbs,node,adj,vis) || false; } else{ if(nbs!=parent) return true; } } return false; } // Function to detect cycle in an undirected graph. public boolean isCycle(int V, ArrayList adj) { int vis[]=new int[V]; for(int i=0;i
@@sumerrawat6947 thanks sir!! Pr ek baat or btadijiye Aap bol rhe ho ki har component ki complexity addup hui hai To sir is hisab se complexity O(c1+2e1) + O(c2+2e2) ..... O(x+2ex ) honi chiye thi? Agr yhi hai to kya ye eqn hi X + O(N+2E) ke equal hai?
@@Yash-uk8ib dekh bhai Lets say we have 4 connected components so total 4 calls will be made complexity of each component for iteration 1: O(N1+2E1) for iteration 2: O(N2+2E2) for iteration 3 O(N3+2E3) for iteration 4 O(N4+2E4) as the number of nodes are different in each componenet total TIME COMPLEXITY = 4 + O(N1+N2+N3+N4) + 2(E1+E2+E3+E4) = 4+O(N + 2E ) or X + O(N+2E) where X is the total number of calls N is total number of nodes in WHOLE GRAPH E is total edges in WHOLE GRAPH
Don't you think all @all that visited array should be sent with reference ! As without reference ! The function check / detect is running for every element / vertex ! As the vis array is a copy in all the dfs calls !
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
Please complete the series ASAP
Hello bhaiya I have doubt that why the time complexity is O(N+2*E) why not O(2*E)
@@Sumeet_100 Because you are going for all nodes N AND(+) visiting all degrees means 2E.
Really very good lecture series. Waiting for the next lectures.
Understood! So fantastic explanation as always, thank you very much!!
Amazing explanation bhaiya really amazing. Was trying to understand it from many source but was not able to understand properly. Really enjoy your teaching. Keep going bhaiya
understood it very well
Your explanation is awesome
Without seeing a code i had doned
Credits goes to striver who has an talent to make it as easy entire dsa for us....❤
understood striver
was able to do this by dfs by myself after watching and getting the concept from last video
Amazing content as always
wah nanhe striver
@@prakhaxr sure, I'll take it as a compliment🙂
Understanding more and more each day that I'm not smart enough to understand this high level logic
Spent 1 year to understand, still haven't understood anything
Bhaiya ur teaching style is awesome.
It really feels good learning from you
Amazing explanation for DFS..
Classic style of Explanation
The way you explained. Just wow 😃😃
kya hi hai bhai..u make to feel the concept..loving ur content so much
"UNDERSTOOD BHAIYA!!"
understood Striver Bhaiya ❤❤
great explanation bhaiya, totally understood
Thanks for the wonderful explanation.
got the intution because of your rotten oranges videos, i felt it is almost similar to that, thanks understood
This question can also be done by using the concept V=E+1 in cyclic undirected graph using dfs
PERFECTTTT STRIVERRR!!!!
UNDERSTOOODDDD
understood bhaiya. Are there more videos coming for Graph in this playlist? It would be very helpful if there are more to come..
But great work..
understood, thanks for this amazing series
Amazing session Understood!!
Understood, Thank you so much
Thank you, Striver 🙂
understood,great explanation
Isn't the both conditions are same inside the loop why we need if condition inside if pls explain...,
Understood bhaiya 👍
will it work fine even for this case where 2 nodes are there each points each other ond forming cycle?
Understood!!More!!✌🏻
Nice explanation, i understood 👍
understood sir very nice
understood striver
understood! Thanks man
Bold me "UNDERSTOOD"
Thank you sir
Thanks for the series
Understood Bhaiya.
Understood sir 🙇♂️
Thank You So Much Sir😇
Simple intution is : It's not the parent still already visited that means cycle exists
Understood 🙌🏻
When is the possible date of completion of the series.
Understood 🙌🔥
Can anyone tell me that why striver has used a vector of array for the visited array instead of a single vector/array in C++ code, or its just mistyped while coding ??
Amazing....... Always
Loved it and understood
understood sir
plz make a video on snake and ladder.love u bro
super duper hit video
Instead of "if(dfs(adjacentNode, node, visited, adj) == true)
return true; ", if we directly return the dfs function, then it is incorrect. Whu so ?
I think It should be same
ya exactly, same doubt, can someone explain please!
in the above statement it the output of the function is true it will directly return it and if you return at last it may or may not return true always
Because detect function will return true or false for every component between one to n,
Lets say first component has no cycle, but second one has a cycle.
But according to your code, it will not go to second component, it will just return false after iterating in first component.
So, if detect function sends a true, then only you should return true, else nothing
in directly returning it will always return something
but in correct method shone in video it will only return true if the dfs function is true
Understood Sir!
Understood Bhaiya
Understood 😄
understood, Thank you so much
thank you Bhaiya
Understood💯
UNDERSTOOD;
understood sirji
understood bhaiya
understood thank you
Understood 🎊
UNDERSTOOD!
Superb
the concept of more than two parent to detect cycle is also good......
If in any adjacency list, if we find two or more visited node during BFS or DFS in a undirected graph then it will have a cycle.
bool detectcycle(int i, vector&vis, vectoradj[]){
bool iscycledetected=false;
vis[i]=1;
int count=0;
for(auto K:adj[i]){
if(vis[K])count++;
}
if(count>1)iscycledetected=true;// this is the check for cycle
for(auto K:adj[i]){
if(!vis[K]){
bool x1=detectcycle(K,vis,adj);
iscycledetected=x1|iscycledetected;
}
}
return iscycledetected;
}
bool isCycle(int V, vector adj[]) {
// This is the main function
vectorvis(V);
for(int i=0; i
bhaiya ji maja agaya
Understoood
why the time complexity is O(N+ 2*E) instead of that why not O(2*E) ??
Cuz a loop runs from 1->n to check whether node is visited or not, if not visited the dfs is performed.
understood sir!
striver please make videos on topic like segment tree
Using non recursive DFS:
class Solution {
public:
bool solver(int V,vector & visited,vector adj[],int child,int parent) {
stack st;
st.push({child,parent});
while(!st.empty())
{
auto p=st.top();
int child=p.first;
int parent=p.second;
st.pop();
if(visited[child]==false)
visited[child]=true;
for(int ele:adj[child])
{
if(!visited[ele])
{
st.push({ele,child});
}
else if(ele!=parent)
return true;
}
}
return false;
}
public:
// Function to detect cycle in an undirected graph.
bool isCycle(int V, vector adj[]) {
vector visited(V,0);
for(int i=0;i
UNDERSTOOD
understood 😁😁
Bhaiya Python code in coding ninja is not accepted but code of other languages are accepted
Understood ++
I'm not understanding why my code is not working on GFG
Understood!
Hey Striver,
I had a doubt, why do we need to store the parent of each node?
Can't we just count the number of neighboring nodes, of a particular node, that are visited,
if the count is more than 1, for any node, then we can conclude that the cycle is present?
Plz let me know if I am missing out on something in my approach.
Following is the implementation for the above logic:
bool detectDfs(int start, vector adj[], int vis[]){
vis[start] = 1;
int visCnt = 0;
bool flag = false;
for(auto it : adj[start]){
if(++visCnt > 1) flag = true;
else if(!vis[it]){
flag = flag || detectDfs(it, adj, vis);
}
if(flag == true) return flag;
}
return flag;
}
bool isCycle(int V, vector adj[]) {
// Code here
int vis[V] = {0};
for(int i = 0; i < V; i++){
if(!vis[i] && detectDfs(i, adj, vis)) return true;
}
return false;
}
No..There is possibility when there are more than one visited and the graph will not contain cycle...Refer GFG Article for such example.
@@kanishkraj5640 I understood @Aniket 's qn but couldn't understand your answer. How can a node be visited, not be the parent, and yet no cycle is formed?
I think, you are right.
In this example you can visit back to the parent node if not stored them.
1 ( 2 3)
2 (1 3)
Here you will go to 2 from 1 and again 1 from 2 and you got your cycle when there is no cycle at all.
No, if u have a graph with one node and 3 outwards edge , then it doesnt mean its a cycle right?
like 1--->2,3,4
so u visit 2,3 from 1 and visit counts become 2 > 1 , does that mean it has a cycle? No
one doubt, why do you write functions under private? any specific reason for that?
you dont want that function to be exposed somewhere else! you specifically want dfs or dfs for this solution class only and other classes if made can have their methods likewise.
yes u can add the function under public too not an issue but as far as clean code is concerned its better to add under private
"Methods that serve as the inner workings of your class and don’t output or display information." read this carefully for private
understood :)
Understood. :)
thanks thanks thanks 😅
A simple question if anyone can help me understand!
If we are given a source node and we are performing DFS on a connected undirected graph(i.e. a single component), how is the time complexity O(N+2E), shoudn't it be just O(2E) which is summation of degrees?
For N nodes we are traversing in the wrost case
@@aprajitakumari3745 because for every node, we are traversing all its adjacent nodes
So In the worst case the 2E will not be done cause worst case means every will be a component in itself
Understood
understood!
can someone please help me to find out why this code is not working..
class Pair{
int first,second;
public Pair(int first,int second){
this.first=first;
this.second=second;
}
}
class Solution {
boolean dfscdetect(int node,int parent,ArrayList adj,int vis[]){
vis[node]=1;
for(int nbs:adj.get(node)){
if(vis[nbs]==0){
return dfscdetect(nbs,node,adj,vis) || false;
}
else{
if(nbs!=parent)
return true;
}
}
return false;
}
// Function to detect cycle in an undirected graph.
public boolean isCycle(int V, ArrayList adj) {
int vis[]=new int[V];
for(int i=0;i
In the dfsdetect function you should return true only when dfsdetect(...) is true, otherwise it will prematurely return false if it is false.
@@d1vyanshu then why for bfs it was working without writing == true ?
can u explain
Why writing the fucntion in private ?
to make it private
understood.
"Understood"
nice
ur awesome
understood
Sir, a small doubt?
Lets say the for loop calls dfs fn X times where X
X + O(N+2E) hoga bro , and X
@@sumerrawat6947 thanks sir!!
Pr ek baat or btadijiye
Aap bol rhe ho ki har component ki complexity addup hui hai
To sir is hisab se complexity
O(c1+2e1) + O(c2+2e2) ..... O(x+2ex ) honi chiye thi?
Agr yhi hai to kya ye eqn hi X + O(N+2E) ke equal hai?
@@Yash-uk8ib dekh bhai
Lets say we have 4 connected components
so total 4 calls will be made
complexity of each component
for iteration 1:
O(N1+2E1)
for iteration 2:
O(N2+2E2)
for iteration 3
O(N3+2E3)
for iteration 4
O(N4+2E4)
as the number of nodes are different in each componenet
total TIME COMPLEXITY =
4 + O(N1+N2+N3+N4) + 2(E1+E2+E3+E4)
= 4+O(N + 2E )
or
X + O(N+2E)
where X is the total number of calls
N is total number of nodes in WHOLE GRAPH
E is total edges in WHOLE GRAPH
@@sumerrawat6947 can you suggest a playlist for time complexity of recursion and graph .
uinderstood bhaiya
Hare Krishna.! Great Video
Don't you think all @all that visited array should be sent with reference ! As without reference ! The function check / detect is running for every element / vertex ! As the vis array is a copy in all the dfs calls !
you are right
arrays are auto referenced
@@aymanalali8983is that Right,
I wanted to know more about this
class Solution {
private:
bool dfs(int node, int parent, vector &vis, vector adj[]){
vis[node] = 1;
for(auto &it : adj[node]){
if(!vis[it]){
if(dfs(it, node, vis, adj) == true) return true;
}
else if(it != parent) return true; // cycle
}
return false;
}
public:
// Function to detect cycle in an undirected graph.
bool isCycle(int V, vector adj[]) {
vector vis(V, 0);
for(int i=0; i
UnderStood
understooddd