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

🚀 Follow me on:

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

[aishwaryshukla]

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

[tech_wizard]

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

[shrutitibile]

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

[myinspiration]

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

[bhushanambhore]

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.

[dibyendudgp]

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

[abhisknowledge]

hlo bhaiya a small doubt in dfs arguement like why there is -1 as parent ?

[harishlodha]

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

[l_ayushkumar]

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

[comp__takshpatel]

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

[newtanagmukhopadhyay]

class Solution {
public:
// Function to detect cycle in an undirected graph.

bool ans = false;

void dfs(int node, int parent, vector<bool>&visited, vector<int>adj[]){

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<int> adj[]) {

vector<bool>visited(V, false);

for(int i=0; i<V; i++){
if(visited[i]==false){
dfs(i, -1, visited, adj);
if(ans)
{return true;}
}
}

return ans;
}
};

[anchalsoni]

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

[_sf_editz]

bhayya ke solution ke saamne kuch bol sakthe he kya

[abdulmajidshaikh]

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

[mitadruchakraborty]

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?

[Rebelx]

Bhaiya mujhe blockchain developer ban sakta hu kya ?

[suar_pilla]

public boolean hasCycleUnDirected(T src) {

return

}

public boolean performDFSCycleDetection(T src) {

// Key as Vertex, Value as its Parent
Map<T, T> visited = new HashMap<>();
Stack<T> stack = new Stack<>();

visited.put(src, null);
stack.add(src);

while (!stack.isEmpty()) {

T pop = stack.pop();

List<T> neighbors = adjList.getOrDefault(pop, Collections.emptyList());

for (T neighbor : neighbors) {
// if vertex is not visited
if {
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;
}