Detect cycle in an undirected graph | Graph coloring method

This video explains how to detect cycle in an undirected graph. I have explained the graph coloring method for this problem. This problem is very frequently asked in coding round as well as in interview. This is highly related to my previous problem on how to detect cycle in a directed graph. So, i will highly recommend you to watch it. As usual, CODE LINK is present below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...
Detect cycle in a directed graph: • Detect cycle in a dire...

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

[@spetsnaz_2]

Most simplest and unique technique. Thank you sir

[@techdose4u]

Welcome :)

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

[@ayushmohan7747]

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

[@techdose4u]

Welcome :)

[@sarveshshirishvhawal7986]

Simplest, understandable code and explanation ever!!!!

[@techdose4u]

Thanks :)

[@mahipalsingh-yo4jt]

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

[@techdose4u]

Nice to know this :)

[@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 :)

[@lifecodesher5818]

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

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

[@RahulChauhan-wi4jv]

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

[@sambhumahato8320]

U Rocked Sir..💖

[@techdose4u]

Thanks shambhu :)

[@thechristchild4625]

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

[@techdose4u]

😅

[@rangapavankumar79]

Truee

[@BaljeetSingh-bx8yj]

Amazing explanation !!

[@techdose4u]

Thanks 😊

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

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?

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

[@spetsnaz_2]

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

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

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

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

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

[@noobninja4882]

awesome explanation sir

[@techdose4u]

Thanks

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

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

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

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

[@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 :)

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

[@falakchhikara7230]

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

[@rahulbhati3079]

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

[@saileshswaminathan9818]

Can this also be used in a directed graph?

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

[@sunilkumar-re7qj]

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

[@ajaygoswami36]

What's to take input

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

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

[@AlanSchooll]

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

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

[@ritikyadav926]

can we use it for directed graph?

[@techdose4u]

Yes. Try it.

[@ritikyadav926]

@@techdose4u Yeh got it

[@impatientgaming9868]

Gooo one

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

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

[@ashutoshshrivastava6521]

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

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

[@ghoshdipan]

Please do try to explain the code more thoroughly

[@techdose4u]

Sure. Doing it now.

[@ayushmehra5059]

Awesome.

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

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

[@antwanwimberly1729]

Kewl!

[@prodiptamondal1758]

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

[@RakeshSingh-yw1bi]

please explain with diagram, not by narrating it.