Detect cycle in a directed graph
Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not.
Example 1:
Input:
Output: 1
Explanation: 3 -> 3 is a cycle
Example 2:
Input:
Output: 0
Explanation: no cycle in the graph
Your task:
You dont need to read input or print anything. Your task is to complete the function isCyclic() which takes the integer V denoting the number of vertices and adjacency list as input parameters and returns a boolean value denoting if the given directed graph contains a cycle or not.
Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)
Constraints:
1 ≤ V, E ≤ 105
solution :
To detect cycle in directed graph , we uses two Boolean array . first which take record of stacks of recursive function and second which take record of how much of vertex are visited till now.
it basically uses the concept of DFS alogithm and backtracking also.
The code is here :
class Solution {
public:
// Function to detect cycle in a directed graph.
bool dfs(vector<bool>&visited , vector<bool>&visiteddfs , vector<int>adj[] , int i)
{
visited[i] = true;
visiteddfs[i] = true;
vector<int>x = adj[i];
for(int k = 0 ; k < x.size() ; k++)
{
if(!visited[x[k]])
{
if(dfs(visited, visiteddfs , adj , x[k]))
return true;
}
else
{
if(visiteddfs[x[k]])
return true;
}
}
visiteddfs[i] = false;
return false;
}
bool isCyclic(int V, vector<int> adj[]) {
vector<bool>visited(V ,false);
vector<bool>visiteddfs(V , false);
for(int i = 0 ; i < V ; i++)
{
if(!visited[i])
{
if(dfs(visited, visiteddfs , adj , i))
return true;
}
}
return false;
}
};
References : https://practice.geeksforgeeks.org/problems/detect-cycle-in-a-directed-graph/1
Comments
Post a Comment