Advertisement
vaibhav1906

Cycle in directed graph

Jul 27th, 2021
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.91 KB | None | 0 0
  1. //Link to the question : https://practice.geeksforgeeks.org/problems/detect-cycle-in-a-directed-graph/1#
  2.  
  3. bool check(vector<int> adj[],vector<int> &visit, int curr, int rank){
  4.  
  5. visit[curr] =rank;
  6. rank++;
  7.  
  8. for(int i = 0; i< adj[curr].size(); i++){
  9. int ncurr = adj[curr][i];
  10. if(visit[ncurr]==-1){
  11. if(check(adj,visit,ncurr,rank)==true)return true;
  12. }
  13. else{
  14. if(visit[ncurr]<rank)return true;
  15. }
  16. }
  17.  
  18. visit[curr] = visit.size()+1;
  19.  
  20. return false;
  21.  
  22. }
  23.  
  24. class Solution
  25. {
  26. public:
  27. //Function to detect cycle in a directed graph.
  28. bool isCyclic(int V, vector<int> adj[])
  29. {
  30. // code here
  31. vector<int>visit(V,-1);
  32.  
  33. for(int i = 0; i<V; i++){
  34. if(visit[i]==-1){
  35. if(check(adj,visit,i,0)==true)return true;
  36. }
  37. }
  38.  
  39. return false;
  40.  
  41. }
  42. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement