Advertisement
imashutosh51

Prerequisite Tasks

Jul 31st, 2022
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. //checking for circle in directed graph
  2. bool ans=true;
  3. void dfs(vector <int> adj[],int i,bool visited[],bool dfs_visited[]){
  4.     visited[i]=true;
  5.     dfs_visited[i]=true;
  6.     for(auto itr:adj[i]){
  7.             if(visited[itr] && dfs_visited[itr]){ans=false; return;}
  8.             if(!visited[itr])
  9.             dfs(adj,itr,visited,dfs_visited);
  10.     }
  11.     dfs_visited[i]=false;
  12. }
  13. class Solution {
  14. public:
  15.     bool isPossible(int n, vector<pair<int, int> >& pre) {
  16.        ans=true;
  17.        vector<int> adj[n];
  18.        for(auto itr:pre){
  19.            adj[itr.second].push_back(itr.first);
  20.        }
  21.        bool visited[n],dfs_visited[n];
  22.        memset(visited,false,sizeof(visited));
  23.        memset(dfs_visited,false,sizeof(dfs_visited));
  24.        for(int i=0;i<n;i++){
  25.            if(!visited[i]){
  26.                dfs(adj,i,visited,dfs_visited);
  27.            }
  28.        }
  29.        return ans;
  30.        
  31.     }
  32. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement