Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Link to the question : https://practice.geeksforgeeks.org/problems/detect-cycle-in-a-directed-graph/1#
- bool check(vector<int> adj[],vector<int> &visit, int curr, int rank){
- visit[curr] =rank;
- rank++;
- for(int i = 0; i< adj[curr].size(); i++){
- int ncurr = adj[curr][i];
- if(visit[ncurr]==-1){
- if(check(adj,visit,ncurr,rank)==true)return true;
- }
- else{
- if(visit[ncurr]<rank)return true;
- }
- }
- visit[curr] = visit.size()+1;
- return false;
- }
- class Solution
- {
- public:
- //Function to detect cycle in a directed graph.
- bool isCyclic(int V, vector<int> adj[])
- {
- // code here
- vector<int>visit(V,-1);
- for(int i = 0; i<V; i++){
- if(visit[i]==-1){
- if(check(adj,visit,i,0)==true)return true;
- }
- }
- return false;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement