Detect cycle in an undirected graph_GRAPH_COLORING

// { Driver Code Starts
#include<bits/stdc++.h>

using namespace std;


 // } Driver Code Ends
/* This function is used to detect a cycle in undirected graph
*  adj[]: array of vectors to represent graph
*  V: number of vertices
*/
bool isCyclic_util(vector<int> adj[], vector<int> visited, int curr)
{
    if(visited[curr]==2)
        return true;
    
    visited[curr] = 1;
    bool FLAG = false;
    for(int i=0;i<adj[curr].size();++i)
    {
        if(visited[adj[curr][i]]==1)
            visited[adj[curr][i]] = 2;
        else
        {
            FLAG = isCyclic_util(adj, visited, adj[curr][i]);
            if(FLAG==true)
                return true;
        }
    }
    return false;
}

bool isCyclic(vector<int> adj[], int V)
{
   vector<int> visited(V,0);
   bool FLAG = false;
   for(int i=0;i<V;++i)
   {
        visited[i] = 1;
        for(int j=0;j<adj[i].size();++j)
        {
            FLAG = isCyclic_util(adj,visited,adj[i][j]);
            if(FLAG==true)
                return true;
        }
        visited[i] = 0;
   }
   return false;
}

// { Driver Code Starts.

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int V, E;
        cin>>V>>E;
        
        // array of vectors to represent graph
        vector<int> adj[V];
        
        int u, v;
        for(int i=0;i<E;i++)
        {
            cin>>u>>v;
            
            // adding edge to the graph
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        cout << isCyclic(adj, V)<<endl;

    }
}
  // } Driver Code Ends

it showing wrong output in this test case-
V = 4, E = 3
0 1
1 2
2 3

what if visited array in the isCyclicUtil is passed by reference, what changes will you make?

@gods-mack did you solve this problem? I am getting the same error

@gods-mack did you solve this problem? I am getting the same error

@shivanik6z No, as you know the main code owner never replied, So I solved it on my own. Its been a long time now.

@gods-mack did you solve this problem? I am getting the same error

@shivanik6z No, as you know the main code owner never replied, So I solved it on my own. Its been a long time now.

this is the isCyclic_Util function that i have derived and is much simpler
i have shown this for directed graph but you can just make this for undirected graph as well and it will work fine.

bool isCyclic_Util(vector<vector<int>>& adj, vector<int>& vis, int curr){
    if(vis[curr] == 2)
        return true;
    
    vis[curr] = 2;
    for(int i=0; i<adj[curr].size(); i++){
        if(vis[adj[curr][i]] != 1 and isCyclic_Util(adj, vis, adj[curr][i]))
            return true;
    }
    
    vis[curr] = 1;
    return false;
}

bool isCyclic(int numCourses, vector<vector<int>>& pre) {
        int n = pre.size();
        vector<vector<int>> adj(numCourses);
        for(int i=0; i<n; i++)
            adj[pre[i][0]].push_back(pre[i][1]);
        
        vector<int> vis(numCourses, 0);
        for(int i=0; i<numCourses; i++){
            if(vis[i] == 0 and isCyclic_Util(adj, vis, i)){
                return false;
            }
        }
        return true;
    }

Consider a case:
V = 4, E = 3
0 1
1 2
0 3
The published code, checks a vertex more than once.
Consider node 0 which has an adjacency list as 0 -> 1 -> 3
while visiting 1 we recur its adjacency list which is 1 -> 0 -> 2
then we mark 0 as 2 and recur adjacency list for 2 and so on till a point we dont find a cycle at node 0, then we begin the same at next node 1.

My point is if the graph is way diverse, the point of detecting a cycle in a undirected graph using this method doesn't seem efficient since
we keep checking a node even when we may have visited it and found no cycle on it but then again we check if a cycle is formed on that very same node in the next iteration (for eg when we checked on 0 traversing node 1 but we still traverse the graph using node 1 latter). This question really bothered me lol.

@gods-mack did you solve this problem? I am getting the same error

@shivanik6z No, as you know the main code owner never replied, So I solved it on my own. Its been a long time now.

Can you share the code?

@gods-mack did you solve this problem? I am getting the same error

@shivanik6z No, as you know the main code owner never replied, So I solved it on my own. Its been a long time now.

this is the isCyclic_Util function that i have derived and is much simpler
i have shown this for directed graph but you can just make this for undirected graph as well and it will work fine.

bool isCyclic_Util(vector<vector<int>>& adj, vector<int>& vis, int curr){
    if(vis[curr] == 2)
        return true;
    
    vis[curr] = 2;
    for(int i=0; i<adj[curr].size(); i++){
        if(vis[adj[curr][i]] != 1 and isCyclic_Util(adj, vis, adj[curr][i]))
            return true;
    }
    
    vis[curr] = 1;
    return false;
}

bool isCyclic(int numCourses, vector<vector<int>>& pre) {
        int n = pre.size();
        vector<vector<int>> adj(numCourses);
        for(int i=0; i<n; i++)
            adj[pre[i][0]].push_back(pre[i][1]);
        
        vector<int> vis(numCourses, 0);
        for(int i=0; i<numCourses; i++){
            if(vis[i] == 0 and isCyclic_Util(adj, vis, i)){
                return false;
            }
        }
        return true;
    }

Consider a case:
V = 4, E = 3
0 1
1 2
0 3
The published code, checks a vertex more than once.
Consider node 0 which has an adjacency list as 0 -> 1 -> 3
while visiting 1 we recur its adjacency list which is 1 -> 0 -> 2
then we mark 0 as 2 and recur adjacency list for 2 and so on till a point we dont find a cycle at node 0, then we begin the same at next node 1.

My point is if the graph is way diverse, the point of detecting a cycle in a undirected graph using this method doesn't seem efficient since
we keep checking a node even when we may have visited it and found no cycle on it but then again we check if a cycle is formed on that very same node in the next iteration (for eg when we checked on 0 traversing node 1 but we still traverse the graph using node 1 latter). This question really bothered me lol.

yes you are right, it is checking again and again , so it's very inefficient.
I am working on this solution, i will send it soon.

@gods-mack did you solve this problem? I am getting the same error

@shivanik6z No, as you know the main code owner never replied, So I solved it on my own. Its been a long time now.

this is the isCyclic_Util function that i have derived and is much simpler
i have shown this for directed graph but you can just make this for undirected graph as well and it will work fine.

bool isCyclic_Util(vector<vector<int>>& adj, vector<int>& vis, int curr){
    if(vis[curr] == 2)
        return true;
    
    vis[curr] = 2;
    for(int i=0; i<adj[curr].size(); i++){
        if(vis[adj[curr][i]] != 1 and isCyclic_Util(adj, vis, adj[curr][i]))
            return true;
    }
    
    vis[curr] = 1;
    return false;
}

bool isCyclic(int numCourses, vector<vector<int>>& pre) {
        int n = pre.size();
        vector<vector<int>> adj(numCourses);
        for(int i=0; i<n; i++)
            adj[pre[i][0]].push_back(pre[i][1]);
        
        vector<int> vis(numCourses, 0);
        for(int i=0; i<numCourses; i++){
            if(vis[i] == 0 and isCyclic_Util(adj, vis, i)){
                return false;
            }
        }
        return true;
    }

Consider a case:
V = 4, E = 3
0 1
1 2
0 3
The published code, checks a vertex more than once.
Consider node 0 which has an adjacency list as 0 -> 1 -> 3
while visiting 1 we recur its adjacency list which is 1 -> 0 -> 2
then we mark 0 as 2 and recur adjacency list for 2 and so on till a point we dont find a cycle at node 0, then we begin the same at next node 1.
My point is if the graph is way diverse, the point of detecting a cycle in a undirected graph using this method doesn't seem efficient since
we keep checking a node even when we may have visited it and found no cycle on it but then again we check if a cycle is formed on that very same node in the next iteration (for eg when we checked on 0 traversing node 1 but we still traverse the graph using node 1 latter). This question really bothered me lol.

yes you are right, it is checking again and again , so it's very inefficient.
I am working on this solution, i will send it soon.

I mean i get it consider a graph that has nodes not connected to anything, which is why this method is considered. Anyways thanks! I'll be trying myself too

@gods-mack did you solve this problem? I am getting the same error

@shivanik6z No, as you know the main code owner never replied, So I solved it on my own. Its been a long time now.

this is the isCyclic_Util function that i have derived and is much simpler
i have shown this for directed graph but you can just make this for undirected graph as well and it will work fine.

bool isCyclic_Util(vector<vector<int>>& adj, vector<int>& vis, int curr){
    if(vis[curr] == 2)
        return true;
    
    vis[curr] = 2;
    for(int i=0; i<adj[curr].size(); i++){
        if(vis[adj[curr][i]] != 1 and isCyclic_Util(adj, vis, adj[curr][i]))
            return true;
    }
    
    vis[curr] = 1;
    return false;
}

bool isCyclic(int numCourses, vector<vector<int>>& pre) {
        int n = pre.size();
        vector<vector<int>> adj(numCourses);
        for(int i=0; i<n; i++)
            adj[pre[i][0]].push_back(pre[i][1]);
        
        vector<int> vis(numCourses, 0);
        for(int i=0; i<numCourses; i++){
            if(vis[i] == 0 and isCyclic_Util(adj, vis, i)){
                return false;
            }
        }
        return true;
    }

Consider a case:
V = 4, E = 3
0 1
1 2
0 3
The published code, checks a vertex more than once.
Consider node 0 which has an adjacency list as 0 -> 1 -> 3
while visiting 1 we recur its adjacency list which is 1 -> 0 -> 2
then we mark 0 as 2 and recur adjacency list for 2 and so on till a point we dont find a cycle at node 0, then we begin the same at next node 1.
My point is if the graph is way diverse, the point of detecting a cycle in a undirected graph using this method doesn't seem efficient since
we keep checking a node even when we may have visited it and found no cycle on it but then again we check if a cycle is formed on that very same node in the next iteration (for eg when we checked on 0 traversing node 1 but we still traverse the graph using node 1 latter). This question really bothered me lol.

yes you are right, it is checking again and again , so it's very inefficient.
I am working on this solution, i will send it soon.

I mean i get it consider a graph that has nodes not connected to anything, which is why this method is considered. Anyways thanks! I'll be trying myself too

i found this is the simplest solution and efficient by check that if the node has already been visited and they have different parent then it is in cycle

bool find_cycle(vector<vector<int>> &graph,int n,int s,vector<int> &visited,int par)
{
    visited[s] = 1;
    
    for (int i = 0;i < graph[s].size();i++)
    {
        if (visited[graph[s][i]] == 0)
        {
            if (find_cycle(graph,n,graph[s][i],visited,s) == true)
                return true;
        } else 
        {
            if (graph[s][i] != par)
                return true;
        }
    }
    
    return false;
}

int Solution::solve(int n, vector<vector<int> > &a) {
    
    int m = a.size();
    
    if (m >= n)
        return 1;
    
    vector<vector<int>> graph;
    graph.resize(n+1);
    
    for (int i = 0;i < m;i++)
    {
        graph[a[i][0]].emplace_back(a[i][1]);
        graph[a[i][1]].emplace_back(a[i][0]);
    }
    
    vector<int> visited;
    visited.resize(n+1,0);
    
    for (int i = 1;i <= n;i++)
    {
        if (visited[i] == 0)
        {
            if (find_cycle(graph,n,i,visited,0) == true)
                return 1;
        }
    }
    
    return 0;
}

If you got TLE use this.

class Solution {
public:

    bool help(vector<int> adj[], vector<int>& visited, int idx,int p)
    {
        visited[idx] = true;
        for(int i = 0; i<adj[idx].size(); i++)
        {
            if(visited[adj[idx][i]]==0)
            {
                if(help(adj,visited,adj[idx][i],idx))
                    return true;
            }
            else
            {
                if(adj[idx][i]!=p || adj[idx][i]==idx)
                    return true;
            }
        }
        return false;
    }
    
	bool isCycle(int V, vector<int>adj[]){
	    // Code here
	    vector<int> visited(V,0);
	   	for(int i = 0; i<V; ++i)
	   	{
	        if(visited[i]==0 && help(adj,visited,i,-1))
	   	       return true;
	   	}
	   	return false;
	}
};

If you got TLE use this.

class Solution {
public:

    bool help(vector<int> adj[], vector<int>& visited, int idx,int p)
    {
        visited[idx] = true;
        for(int i = 0; i<adj[idx].size(); i++)
        {
            if(visited[adj[idx][i]]==0)
            {
                if(help(adj,visited,adj[idx][i],idx))
                    return true;
            }
            else
            {
                if(adj[idx][i]!=p || adj[idx][i]==idx)
                    return true;
            }
        }
        return false;
    }
    
	bool isCycle(int V, vector<int>adj[]){
	    // Code here
	    vector<int> visited(V,0);
	   	for(int i = 0; i<V; ++i)
	   	{
	        if(visited[i]==0 && help(adj,visited,i,-1))
	   	       return true;
	   	}
	   	return false;
	}
};

Glad to see this thread still active! I'll revise my stuff lol thanks for the sol.