Detect Cycle in Undirected Graph | Using DFS | Cycle detection in Graph | DSA-One Course #77

Hey guys, In this video, We're going to solve an important problem in Graphs called: Detect cycle in an Undirected Graph
Practice here: practice.geeksforgeeks.org/pr...
💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
🥳 Join our Telegram Community:
Telegram channel: telegram.me/realanujbhaiya
Telegram group: telegram.me/dsa_one
🚀 Follow me on:
Instagram: / anuj.kumar.sharma
Linkedin: / sharma-kumar-anuj
Twitter: / realanujbhaiya
📚 Complete DSA Playlist: • DSA-One Course - The C...
Complete Android Development Playlist: • Android Development Tu...
Hashtags:
#anujbhaiya #dsaone
Tags:
detect cycle in undirected graph
detect cycle in an undirected graph
detect cycle in a undirected graph
cycle detection in undirected graph
anuj bhaiya
cycle detection in graph
detect cycle in graph
cycle in undirected graph
detect cycle in a directed graph
cycle in graph
graph data structure
graph dsa
undirected graph
cycle detection
anuj bhaiya java
cycle detection in directed graph
cycle in a graph
dsa one
cycle detection graph
graph in java
graph playlist
graphs dsa
cycle detection dfs
cycle detection striver
dfs
dfs graph
dfs in graph
dfs traversal
diameter of binary tree
dsa
find cycle in graph
finding cycle in a graph
floyd cycle detection
graph coding
graph cycle detection
graph in data structure
graph in dsa
java anuj bhaiya

[@aishwaryshukla8880]

The way you do dry run after explaining the code, showing the white board side by side to the code editor is amazing! I don't know how did you get that idea but please know that it truly ensures that we have understood the code completely and easily. Please continue the good work and I hope you get whatever you want!

[@JRK_RIDES]

That DRY run at the end was very useful, would've been a little confused otherwise

[@saniyapathan8968]

Best Explanation ever!

[@tech_wizard9315]

Please make a 60day roadmap for DSA beginner to crack tech giant's like Microsoft linkedin etc companies in 60days

[@mnnitallahabad6753]

Impossible

[@jatinkashyap9986]

Not impossible ​@@mnnitallahabad6753

[@SauravNrai]

You are amazing... Thank you so much

[@akankshasrivastava3354]

I like your dedication sir🙌

[@sandeepdhiman9887]

very well explained

[@saritaprasad4295]

very useful

[@patelvivekshirinbhai5241]

greate expaination

[@shrutitibile5473]

Sir all concept ke video bhejo dsa ke bahot help ho rhe hai isase

[@Ravi-moq-6589]

The best❤

[@ishantbhatia3194]

nice

[@piyushagarwal8458]

Guru Ji, Pranam !!

[@AnujBhaiya]

Pranam bro 🤙

[@myinspiration4642]

Hi Anuj, in DFS how we are maintaining parent node, Please explain

[@chocolateandmath497]

int parent, we are not maintaining all parents

[@dibyendudgp10]

I was thinking, union Find bhi to use kar sakte hai isme ? Ya koi edge case hai, jo unionFind cover nahi karega is case mei ? Uska complexity bhi to isse kam hi ana chahiye

[@harishlodha8794]

Sir background video recorder app se record Kiya hua video app developer ke pass bhi store hota hai kya

[@govindgupta290]

exact same is not working for me

[@mrrishiraj88]

🙏🙏

[@gauravbanerjee2898]

Happy Teacher's day Bhaiya ❤️

[@bhushanambhore8378]

Sir one doubt, where are you updating the parent variable of every vertex in your code? Initially, you set -1 as a parent of 0th vertex but after traversing the graph parent variable is supposed to be updated every time after visiting vertexes.

[@divyanshpant169]

It's updated in the dfs function call when we pass V as parent argument

[@piyushanand3451]

Same doubt.. please explain if you got it cleared.

[@siddhantchavan1370]

when he recursively calls dfs, he passes the current node as the parent to the function.

[@anchalsoni5892]

bhaiya smjh toh aa gya tha pr saare testcases pass nhi kiye

[@abdulmajidshaikh300]

bhaiya code full nehi dekha jarahey , please when show code u can full display

[@sayitavii]

search it on geeks for geeks you'll get the code almost the same

[@comp_131_takshpatel9]

Aapako bhaiya video me at run time coding karana chahiye , kyuki it is better

[@l11_ayushkumar80]

sir code ke waqt word wrap kar diya karo naa thoda asaan ho jaata hai

[@_sf_editz1870]

bhayya ke solution ke saamne kuch bol sakthe he kya

[@mitadruchakraborty5184]

Bhai aapne jo code likha hai... usme I think "if(neighbor!=parent)" condition "if(!vis[neighbor])" condition se pahle hoga.... kiuki mai ye changes kiya then only mera 210/210 test cases run kar raha hai... Bhai can you check?

[@annanyavijay4267]

Mera to fir bhi run nhi kr rha

[@raht9578]

if nhi else if lagao

[@Rebelx27]

Bhaiya mujhe blockchain developer ban sakta hu kya ?

[@suar_pilla]

aap kya ban paoge Bhaiya kaise bolega bhaya? Chu**** thik banega

[@avinashsharma6286]

always give the code

[@newtanagmukhopadhyay4716]

class Solution { public: // Function to detect cycle in an undirected graph. bool ans = false; void dfs(int node, int parent, vector&visited, vectoradj[]){ visited[node] = true; for(int neighbour : adj[node]){ if(neighbour == parent) continue; if(visited[neighbour]==true){ ans = true; return; } dfs(neighbour, node, visited,adj); } return; } bool isCycle(int V, vector adj[]) { vectorvisited(V, false); for(int i=0; i

[@Akaash449]

Kya Bhaiya aapka last name hai?

[@abhi36292]

no

[@abhi36292]

its bade bhaiya

[@Akaash449]

@@abhi36292 😂😂

[@suar_pilla]

public boolean hasCycleUnDirected(T src) { return performDFSCycleDetection(src); } public boolean performDFSCycleDetection(T src) { // Key as Vertex, Value as its Parent Map visited = new HashMap(); Stack stack = new Stack(); visited.put(src, null); stack.add(src); while (!stack.isEmpty()) { T pop = stack.pop(); List neighbors = adjList.getOrDefault(pop, Collections.emptyList()); for (T neighbor : neighbors) { // if vertex is not visited if (!visited.containsKey(neighbor)) { visited.put(neighbor, pop); stack.add(neighbor); } else { // when vertex is already visited, //check who introduced the current element T vertexIntroducedBy = visited.get(pop); // parent of the current element // if parent is a neighbor or null (in case of starting position) // then its fine else there is a cycle. // in the case of A B, A's parent is null, // but B's parent is A. so when B's neighbors are being evaluated, // A is supposed to come as A is B's neighbor, // but it will not be a cycle as B as introduced by A if (vertexIntroducedBy == neighbor || vertexIntroducedBy == null) continue; else return true; } } } return false; }