Detect cycle in an undirected graph | Graph coloring method

[@prasannakumarz]

This channel will rock in future for the stuff it has.........!

[@techdose4u]

Thanks :)

[@vrushalijadhav2062]

Everything that I have learned about graphs so far is from your videos. Concise and thorough. Thank you!

[@sujalhansda8285]

nice dp you are an inspiration to young girls

[@rahulchudasama9363]

Many thank you sir for teaching. I have tried to understand this algo but it took long time to implement it in code(Java) and i gave up. Convert back 2 to 1 I found that is difficult for me. I find BFS with graph coloring is the best to approach this.

[@techdose4u]

👍

[@tanishksharma7339]

Hey can you please help me, I am trying in Java and getting error ide.geeksforgeeks.org/H9cOiEmow6

[@ayushminanayak5352]

At 3:01 when the value of [0] changes from 2 to 1 I think the value of [1] will also Change from 1 to 0

[@harshpatel1385]

I am in 2nd year sir your video's are very helpful to me. It will help me to crack interview. Good bless you sir

[@techdose4u]

Thanks :)

[@spetsnaz_2]

Most simplest and unique technique. Thank you sir

[@techdose4u]

Welcome :)

[@mahipalsingh-yo4jt]

your videos helped me a lot in developing thought process....

[@techdose4u]

Nice to know this :)

[@sarveshshirishvhawal7986]

Simplest, understandable code and explanation ever!!!!

[@techdose4u]

Thanks :)

[@ayushmohan7747]

Just Awesome bro, You made Graph DS easy for me . Thanks, God Bless You :)

[@techdose4u]

Welcome :)

[@manojg4451]

Another trick we can use is that a graph with out any cycle is considered a tree and it has n-1 edges, So if the graph has more than n-1 edges it has a cycle

[@kaushikgopu6639]

this will only work if graph is connected.

[@RahulChauhan-wi4jv]

what changes would you make to the iscyclicUtil function if the visited array was passed by reference?

[@saifmohammed1481]

In my opinion we just need 2 colours for visited i.e 0 and 1 denoting unvisited and visited. If a node encounters visited value 1 and that vertex is not it's caller in DFS, then it's a cycle . In directed graphs though it makes sense to have 3 colours. Don't you think ??

[@Rahul-sx5zo]

at 2:57 after all the nodes for 1 have been processed and we return back to node 0. in visited[0] is changed to 1 but you forgot to change visited[1] back to 0

[@techdose4u]

Yes I might have 😅

[@Rahul-sx5zo]

@@techdose4u can you verify my code comment i made, please?

[@vankshubansal6495]

We can also pass the visited vector by reference. We just need to make sure that before calling other children, visited[curr] is set to 1. Attaching the accepted code for reference. bool dfs2(int V, vector adj[], int sv, vector& visited) { for(auto neigh: adj[sv]) { visited[neigh]++; if(visited[neigh] == 3) return true; else if(visited[neigh] == 1) { if(dfs2(V, adj, neigh, visited)) return true; } visited[sv] = 1; } return false; } bool isCycle(int V, vectoradj[]) { vector visited(V, 0); for(int i = 0; i < V; i++) { if(visited[i] == 0) { visited[i] = 1; if(dfs2(V, adj, i, visited) == true) return true; } } return false; }

[@devcodes6495]

Can you elaborate a little on why we did that??

[@lifecodesher5818]

Thanks so much for such clear explanation!! sending lots of good wishes to you...

[@AlanSchooll]

simple solution is keep track of previous node and you cannot move to nodes previous node.

[@sambhumahato8320]

U Rocked Sir..💖

[@techdose4u]

Thanks shambhu :)

[@thechristchild4625]

thank so much sir.u are like a god for us:

[@techdose4u]

😅

[@rangapavankumar79]

Truee

[@shravanreddy2557]

Sir please make a video on finding number of islands in the given 2d matrix

[@techdose4u]

Yea....i will add it in my to-do queue list. Okay.

[@shravanreddy2557]

@@techdose4u Thank you :)

[@falakchhikara7230]

I think this coloring method is for directed and visited method is for undirected

[@abhireddy8164]

Please add to your queue sir.find words in a dictionary from 2d character array recursively moving 8 directions.i.e word boggle problem

[@techdose4u]

Okay

[@sandeepnallala48]

sir same method we can use for directed graphs also sir ?? by changing the condition from if(vis[u] == 2) to if(vis[u] == 1) return true; and removing the if condition in util fun for loop ?

[@ajithpalani5139]

I think there is no need of outer for loop in isCyclic function. If I'm wrong please correct me . Thank you in advance.

[@Sky-nt1hy]

making the node from 1 to 2 is actually for taking care of the "adjacent" node so that two adjacent nodes are not counted as a cycle right?

[@BaljeetSingh-bx8yj]

Amazing explanation !!

[@techdose4u]

Thanks 😊

[@impatientgaming9868]

Gooo one

[@mahesh_kok]

better approach is to use prev variable: Python code for that is def detect_cycle_for_undirected(graph): visited = set() def dfs(vertex, prev): if vertex in visited: print("found cycle for vertex: ", vertex) return False visited.add(vertex) for neighbor in graph[vertex]: if neighbor == prev: continue if not dfs(neighbor, vertex): return False return True return "No cycle detected" if dfs(0, -1) else "Cycle detected" cycle_leetcode_data = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] no_cycle_leetcode_data = [[0, 1], [0, 2], [0, 3], [1, 4]] graph = defaultdict(list) for src, dest in cycle_leetcode_data: graph[src].append(dest) graph[dest].append(src) print(detect_cycle_for_undirected(graph))

[@sumitghewade2002]

Hi Surya, I tried to implement the code but it's returning true for the graph which doesn't have a cycle. Can you tell what might be going wrong and in the GitHub link also some people have mentioned that the answer is wrong for graphs that don't have a cycle.

[@techdose4u]

I will check it once and maybe I will update the code.

[@Sky-nt1hy]

Sir!!!! Thanks for your video! I have one question. If I pass by value the visit array, then it gives me TLE on any judge site. Is this just for the sake of knowledge? Or is there any other way (global visit array) to make this work?

[@techdose4u]

You need to pass by reference so that a new copy is not created. Passing variables by value in recursion call consumes a lot of time.

[@Sky-nt1hy]

@@techdose4u I've been working on how to do by pass by reference for hours but keep failing...since it is 3 colorable, it's really confusing at where in the function I should decrement or set 0 for visit[curr]

[@Rahul-sx5zo]

bool isCyclic(int V, vector adj[]){ vector vis(V,0); for(int i = 0; i < V; i++){ if(isCyclicUtil(adj,vis,i)){ return true; } } return false; } since we mark visited for every node as 1 before calling the isCyclicUtil function on its adjacent nodes, can this be an alternative to that? where we pass the node itself to isCyclicUtil?

[@noobninja4882]

awesome explanation sir

[@techdose4u]

Thanks

[@aditikhandelwal135]

Just amazing!!!

[@mvkisshore]

Thanks for the nice content. Can someone share with me what is the name of the software which used to write on the screen with a mouse?

[@ghoshdipan]

Please do try to explain the code more thoroughly

[@techdose4u]

Sure. Doing it now.

[@akshatsuwalka5759]

TLE in InterviewBit below is the same code bool isCyclic_util(vector adj[], vector visited, int curr) { if(visited[curr]==2) return true; visited[curr] = 1; bool FLAG = false; for(int i=0;i

[@MSCSJhabar]

Sir can't we detect cycle by simply traversing using DFS or BFS ?

[@techdose4u]

Yes. We can

[@MSCSJhabar]

@@techdose4u okay sir, thanks for the reply 🙂

[@saileshswaminathan9818]

Can this also be used in a directed graph?

[@sunilkumar-re7qj]

Why this method is not working in java..... i have converted the same code to java....even then it is not accepting

[@ravikumarkamble6403]

why we use this method ? previous one not?

[@techdose4u]

That means visited our unvisited I think.

[@ravikumarkamble6403]

@@techdose4u previous one means detect cycle in directed graph

[@ashutoshshrivastava6521]

this algorithm is not working for test case B : [ [1, 2] [1, 3] [2, 3] ]

[@sunnychy86]

Sir, where did you apply "pass by value" method in the code?

[@swappy4515]

I guess it's worked internally in recursive call I might be wrong .

[@yitingg7942]

Can I ask which leetcode question is this ? I can't find it.

[@techdose4u]

Search for some cycle detection problem Most probably you will get this. But I took this from geeksforgeeks

[@yitingg7942]

@@techdose4u Oh I see. I couldn't find good problems that are closely related to this.

[@lifecodesher5818]

This is using dfs too right? asking because in my assignment I have to solve this question using both dfs and bfs

[@ayushgarg5929]

Yes , it is DFS

[@ritikyadav926]

can we use it for directed graph?

[@techdose4u]

Yes. Try it.

[@ritikyadav926]

@@techdose4u Yeh got it

[@rahulbhati3079]

is there need of that loop of j in "isCyclic" bcoz we can get in above loop also

[@ayushme53]

Awesome.

[@antwanwimberly1729]

Kewl!

[@ajaygoswami36]

What's to take input

[@saitejdandge2315]

Why don't we apply the dfs function directly on the nodes, instead of their neighbors ? iterate every node and see if this dfs(node) doesnt return true; private static boolean dfs(Integer curr, int[] visited, Map graph) { if (visited[curr] == 2) return true; visited[curr] = 1; if (graph.get(curr) != null) for (Integer n : graph.get(curr)) { if (visited[n] == 1) { visited[n] = 2; } else if (dfs(n, visited, graph)) return true; //marking current to 1 again visited[curr] = 1; } visited[curr] = 0; return false; }

[@amar229832]

Even I have this question. Did you find solution to it ?

[@RakeshSingh-yw1bi]

please explain with diagram, not by narrating it.

[@prodiptamondal1758]

Here is the simpler version code: ideone.com/zWqcWq

[@ayushgarg5929]

Not so efficient...could have easily understood by just passing its parent node in every iteration..and then check whether the children is matching with parent or not...if so , then we won't include that node...rather we will move to another neighbor if it is present...

[@techdose4u]

There are other methods to solve but Coloring is also efficient.

[@cedarpan5305]

​@@techdose4u I also think the presented solution is bit more complicated than the "passing parent" approach. I have also heard there is another approach using disjoint sets. If possible, can you do a video to compare all different solutions for this problem in the future?

[@techdose4u]

@@cedarpan5305 I have already explained cycle detection in disjoint set. Please watch that. When I come back to graph playlist again then I will add some more videos.

[@cedarpan5305]

@@techdose4u Thank you! I will check out the disjoint set video.

[@spetsnaz_2]

Code Link : techdose.co.in/detect-cycle-in-an-undirected-graph/