G-12. Detect a Cycle in an Undirected Graph using DFS | C++ | Java

[@takeUforward]

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

[@darveshchhatani1411]

Please complete the series ASAP

[@Sumeet_100]

Hello bhaiya I have doubt that why the time complexity is O(N+2*E) why not O(2*E)

[@tasneemayham974]

@@Sumeet_100 Because you are going for all nodes N AND(+) visiting all degrees means 2E.

[@dipaligangawane980]

Really very good lecture series. Waiting for the next lectures.

[@cinime]

Understood! So fantastic explanation as always, thank you very much!!

[@harshvardhansingh2272]

understood striver was able to do this by dfs by myself after watching and getting the concept from last video Amazing content as always

[@prakhaxr]

wah nanhe striver

[@singhharsh8019]

@@prakhaxr sure, I'll take it as a compliment🙂

[@abhinavtomar8518]

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

[@vikasbagri1225]

understood it very well Your explanation is awesome

[@selva-qs9dw]

Without seeing a code i had doned Credits goes to striver who has an talent to make it as easy entire dsa for us....❤

[@casinarro]

It really feels good learning from you

[@rachitchaddha999]

Bhaiya ur teaching style is awesome.

[@DivineVision201]

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..

[@anushravishankar9741]

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

[@mount2020]

kya hi hai bhai..u make to feel the concept..loving ur content so much

[@jaishriharivishnu]

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

[@vikramragunathan6392]

The way you explained. Just wow 😃😃

[@VikasBagri-i5j]

understood, thanks for this amazing series

[@vishankpathariya5926]

great explanation bhaiya, totally understood

[@anshusharma11]

Thanks for the wonderful explanation.

[@muskangupta5873]

got the intution because of your rotten oranges videos, i felt it is almost similar to that, thanks understood

[@tasneemayham974]

PERFECTTTT STRIVERRR!!!! UNDERSTOOODDDD

[@KUMARSAURABH-s5i]

Amazing session Understood!!

[@AjayYadav-xi9sj]

When is the possible date of completion of the series.

[@chandramoulipanyam5805]

Classic style of Explanation

[@koushikkumar481]

understood Striver Bhaiya ❤❤

[@rishabhgupta9846]

understood,great explanation

[@DevashishJose]

Understood, Thank you so much

[@fairoossahfeerulwasihf1139]

will it work fine even for this case where 2 nodes are there each points each other ond forming cycle?

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@sripriyapotnuru5839]

Thank you, Striver 🙂

[@RVcalisthenics]

understood striver

[@jagratgupta8392]

understood sir very nice

[@shivanshsingh176]

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

[@devanshchauhan7065]

ya exactly, same doubt, can someone explain please!

[@gautamsingh2599]

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

[@Jaydeeeeeeep]

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

[@vijaymehrotra3236]

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

[@AgrimArtofficial]

This question can also be done by using the concept V=E+1 in cyclic undirected graph using dfs

[@roshansah691]

Nice explanation, i understood 👍

[@abhichi]

Understood!!More!!✌🏻

[@codeman3828]

Thanks for the series

[@supriyamanna715]

understood! Thanks man

[@RohitKumar-dz8dh]

Understood 😊

[@govindsharma7696]

Understood bhaiya 👍

[@adebisisheriff159]

Amazing....... Always

[@UECAshutoshKumar]

Thank you sir

[@nathonluke4058]

Loved it and understood

[@them.pranay7196]

super duper hit video

[@codewithom11]

Thank You So Much Sir😇

[@subhadeepghosh2813]

plz make a video on snake and ladder.love u bro

[@sumeetubale3923]

why the time complexity is O(N+ 2*E) instead of that why not O(2*E) ??

[@gouravchaki7990]

Cuz a loop runs from 1->n to check whether node is visited or not, if not visited the dfs is performed.

[@utkarshpatidar167]

Understood 🙌🏻

[@debanjan10]

understood sir

[@fmkhandwala39]

UNDERSTOOD!

[@Learnprogramming-q7f]

thank you Bhaiya

[@fadebeyond]

Understood Bhaiya.

[@parshchoradia9909]

Understood Sir!

[@coolgaurav5163]

Understoood

[@ANURAGSINGH-nl2ll]

understood thank you

[@shubhankarmondal8690]

Understood 🙌🔥

[@parthdurgude2617]

understood!

[@harshwardhanpatki846]

Understood sir 🙇‍♂️

[@Joy-b6r]

Isn't the both conditions are same inside the loop why we need if condition inside if pls explain...,

[@utsavkumar6048]

understood sirji

[@vaibhavchauhan1930]

understood, Thank you so much

[@adityasaxena6971]

Understood💯

[@sanketmudholkar2889]

Bold me "UNDERSTOOD"

[@tahmidulislamomi1398]

Superb

[@mriduljain6809]

Understood Bhaiya

[@himanshugupta-mz2yk]

Bhaiya Python code in coding ninja is not accepted but code of other languages are accepted

[@TravelTracksByDebo]

understood bhaiya

[@Anony.musk01]

one doubt, why do you write functions under private? any specific reason for that?

[@omkarshendge5438]

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

[@pratapsingh9638]

striver please make videos on topic like segment tree

[@atharvadeshmukh6328]

Understood 😄

[@yashgupta6797]

understood sir!

[@codewithsahil978]

bhaiya ji maja agaya

[@lineshmalkam224]

understood

[@manasranjanmahapatra3729]

Understood!

[@shreyarawatvlogs6920]

I'm not understanding why my code is not working on GFG

[@sarangkumarsingh7901]

Understood

[@mriduljain1981]

understood.

[@ashishbhardwaj4334]

UNDERSTOOD

[@DilpreetSingh-cs7yz]

Why writing the fucntion in private ?

[@udaypratapsingh8923]

to make it private

[@pihus3498]

understood :)

[@Niki_0011]

Understood ++

[@kritisingh3194]

Understood. :)

[@VEDANSHSHARMA-o6k]

ur awesome

[@ritikkoshta5792]

understood 😁😁

[@Simran_048]

Simple intution is : It's not the parent still already visited that means cycle exists

[@Yash-uk8ib]

Sir, a small doubt? Lets say the for loop calls dfs fn X times where X

[@sumerrawat6947]

X + O(N+2E) hoga bro , and X

[@Yash-uk8ib]

@@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?

[@sumerrawat6947]

@@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

[@MdSarfrazcs]

@@sumerrawat6947 can you suggest a playlist for time complexity of recursion and graph .

[@gururajsavalgi4496]

nice

[@abhinavanand1904]

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 ??

[@poorvikac3280]

Seems like a tying mistake. Passing int vis[] to a vector vis[] doesn't make sense and will throw an error.

[@kholiyamails1257]

thanks thanks thanks 😅

[@ayushgarg9099]

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?

[@aprajitakumari3745]

For N nodes we are traversing in the wrost case

[@anshumaan1024]

@@aprajitakumari3745 because for every node, we are traversing all its adjacent nodes

[@reee896]

So In the worst case the 2E will not be done cause worst case means every will be a component in itself

[@aniket6676]

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]

No..There is possibility when there are more than one visited and the graph will not contain cycle...Refer GFG Article for such example.

[@sviswesh3555]

@@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?

[@shripandey4120]

I think, you are right.

[@illusionhex1200]

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.

[@arindammandal1513]

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

[@anonymousboy2868]

understooddd

[@akashsahu2571]

yws

[@AniketSharma-ct5fv]

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 !

[@rutwikmore7462]

you are right

[@aymanalali8983]

arrays are auto referenced

[@Jaydeeeeeeep]

​@@aymanalali8983is that Right, I wanted to know more about this

[@SatyamKumar-bw4vi]

Hare Krishna.! Great Video

[@addityasharma6426]

understood :-)

[@kushagramishra3026]

"Understood"

[@isheep9025]

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

[@anuraggulati2167]

uinderstood bhaiya

[@anuragC819]

sir ek saath release kar do na videos (T - T)

[@artifice_abhi]

understood++;

[@gamerglobe4839]

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

[@d1vyanshu]

In the dfsdetect function you should return true only when dfsdetect(...) is true, otherwise it will prematurely return false if it is false.

[@lakshsinghania]

@@d1vyanshu then why for bfs it was working without writing == true ? can u explain