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
If you dont understand this, that means you need to first have sold understanding of Recursion, Linked List, and Tree problems. Once you get those, then only come to graphs. DONT GIVE UP
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
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
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 ??
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?
@@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
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.
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! So fantastic explanation as always, thank you very much!!
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🙂
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
Bhaiya ur teaching style is awesome.
It really feels good learning from you
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
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
If you dont understand this, that means you need to first have sold understanding of Recursion, Linked List, and Tree problems. Once you get those, then only come to graphs. DONT GIVE UP
Amazing explanation for DFS..
Thanks for the wonderful explanation.
Amazing session Understood!!
understood, thanks for this amazing series
great explanation bhaiya, totally understood
"UNDERSTOOD BHAIYA!!"
understood,great explanation
PERFECTTTT STRIVERRR!!!!
UNDERSTOOODDDD
Thank you, Striver 🙂
got the intution because of your rotten oranges videos, i felt it is almost similar to that, thanks understood
Understood, Thank you so much
Understood bhaiya 👍
Understood!!More!!✌🏻
understood Striver Bhaiya ❤❤
understood! Thanks man
Nice explanation, i understood 👍
Thank you so much for the Video!!!!
Thanks for the series
Loved it and understood
understood sir very nice
Understood Sir!
Understood sir 🙇♂️
Thank You So Much Sir😇
Thank you sir
Amazing....... Always
Understood 🙌🔥
Bold me "UNDERSTOOD"
Understood Bhaiya.
Understood 🙌🏻
This question can also be done by using the concept V=E+1 in cyclic undirected graph using dfs
understood sir
understood, Thank you so much
Understood💯
Understood 😄
Understood 🎊
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 Bhaiya
Understoood
understood thank you
understood sir!
UNDERSTOOD!
UNDERSTOOD;
understood striver
super duper hit video
thank you Bhaiya
Superb
understood sirji
understood bhaiya
understood 😁😁
bhaiya ji maja agaya
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
Hare Krishna.! Great Video
understood!
UNDERSTOOD
plz make a video on snake and ladder.love u bro
Understood!
understood :)
understood.
Understood
Understood. :)
understood
thanks thanks thanks 😅
Simple intution is : It's not the parent still already visited that means cycle exists
Understood ++
Isn't the both conditions are same inside the loop why we need if condition inside if pls explain...,
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
ur awesome
nice
striver please make videos on topic like segment tree
When is the possible date of completion of the series.
will it work fine even for this case where 2 nodes are there each points each other ond forming cycle?
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
understooddd
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 ??
uinderstood bhaiya
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.
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
understood :-)
understood++;
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
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"
Bhaiya Python code in coding ninja is not accepted but code of other languages are accepted
If possible bring 2-3 videos per day
Might as well ask him to leave his full time job for your convenience.
@@bruvhellnah gand mara , tere se Bola hai Kuch? English aata hai ?? Nhi aata toh juss go n check the meaning of if possible ,
@@bruvhellnah destroy in second 🤣🤣🤣🤣🤣🤣🤣🤣
@@bruvhellnah 😂😂😂
🙄🙏
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 .
UnderStood
Why writing the fucntion in private ?
to make it private