Detect Cycle in Undirected Graph | Using DFS | Cycle detection in Graph | DSA-One Course #77
Vložit
- čas přidán 17. 03. 2022
- 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
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!
That DRY run at the end was very useful, would've been a little confused otherwise
Best Explanation ever!
Please make a 60day roadmap for DSA beginner to crack tech giant's like Microsoft linkedin etc companies in 60days
Impossible
Not impossible @@mnnitallahabad6753
You are amazing... Thank you so much
I like your dedication sir🙌
Sir all concept ke video bhejo dsa ke bahot help ho rhe hai isase
very well explained
greate expaination
very useful
Sir background video recorder app se record Kiya hua video app developer ke pass bhi store hota hai kya
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
The best❤
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.
It's updated in the dfs function call when we pass V as parent argument
Same doubt.. please explain if you got it cleared.
when he recursively calls dfs, he passes the current node as the parent to the function.
Guru Ji, Pranam !!
Pranam bro 🤙
nice
Hi Anuj, in DFS how we are maintaining parent node, Please explain
int parent, we are not maintaining all parents
exact same is not working for me
🙏🙏
Happy Teacher's day Bhaiya ❤️
bhaiya smjh toh aa gya tha pr saare testcases pass nhi kiye
Aapako bhaiya video me at run time coding karana chahiye , kyuki it is better
bhaiya code full nehi dekha jarahey , please when show code u can full display
search it on geeks for geeks you'll get the code almost the same
sir code ke waqt word wrap kar diya karo naa thoda asaan ho jaata hai
bhayya ke solution ke saamne kuch bol sakthe he kya
Bhaiya mujhe blockchain developer ban sakta hu kya ?
aap kya ban paoge Bhaiya kaise bolega bhaya? Chu**** thik banega
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?
Mera to fir bhi run nhi kr rha
if nhi else if lagao
always give the code
Kya Bhaiya aapka last name hai?
no
its bade bhaiya
@@abhi36292 😂😂
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
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;
}