Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save SuryaPratapK/5917ab6491edc77d55cc9a85570d34cb to your computer and use it in GitHub Desktop.
Save SuryaPratapK/5917ab6491edc77d55cc9a85570d34cb to your computer and use it in GitHub Desktop.
// { 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
@Rahul-Chauhan21
Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment