« back

Detect Cycle using DSU

Tags : disjoint-set, graph, geeksforgeeks, cpp, medium

Problem Statement - link #

Given an undirected graph with V nodes and E edges. The task is to check if there is any cycle in undirected graph. Note: Solve the problem using disjoint set union(dsu).

Your Task:

You don’t need to read or print anyhting. Your task is to complete the function detectCycle() which takes number of vertices in the graph denoting as V and adjacency list denoting as adj and returns 1 if graph contains any cycle otherwise returns 0.

Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Input: 


Output: 1
Explanation: There is a cycle between 0->2->4->0

Example 2:

Input: 


Output: 0
Explanation: The graph doesn't contain any cycle

Constraints #

Solutions #

class Solution
{
    public:
    vector<int> par;
    vector<int> rank;
    int find(int x){
        if(par[x]!=x){
            par[x]=find(par[x]);
        }
        return par[x];
    }
    //Function to merge two nodes a and b.
    bool unionCycle( int a, int b) 
    {
        //code here
        a = find(a);
        b = find(b);
        if(a==b) return true;
        if(rank[a]>rank[b])
            par[b]=a;
        else par[a]=b;
        if(rank[a]==rank[b]) rank[a]++;
        return false;
    }
    //Function to detect cycle using DSU in an undirected graph.
	int detectCycle(int V, vector<int>adj[])
	{
	    // Code here
	    par.resize(V);
	    rank.resize(V);
	    for(int i=0;i<V;i++) { par[i]=i; rank[i]=0; }
	    
	    for(int u=0;u<V;u++)
	        for(int v: adj[u])
	            if(u<v && unionCycle(u,v))
	                return true;
	    return false;
	    
	    
	}
};