Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //checking for circle in directed graph
- bool ans=true;
- void dfs(vector <int> adj[],int i,bool visited[],bool dfs_visited[]){
- visited[i]=true;
- dfs_visited[i]=true;
- for(auto itr:adj[i]){
- if(visited[itr] && dfs_visited[itr]){ans=false; return;}
- if(!visited[itr])
- dfs(adj,itr,visited,dfs_visited);
- }
- dfs_visited[i]=false;
- }
- class Solution {
- public:
- bool isPossible(int n, vector<pair<int, int> >& pre) {
- ans=true;
- vector<int> adj[n];
- for(auto itr:pre){
- adj[itr.second].push_back(itr.first);
- }
- bool visited[n],dfs_visited[n];
- memset(visited,false,sizeof(visited));
- memset(dfs_visited,false,sizeof(dfs_visited));
- for(int i=0;i<n;i++){
- if(!visited[i]){
- dfs(adj,i,visited,dfs_visited);
- }
- }
- return ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement