207. Course Schedule | leetcode solution | detect cycle in directed graph using dfs

on

 207. Course Schedule

 There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.
solution: 

class Solution {
public:
    bool dfs(vector<bool>&visited , vector<bool>&visiteddfs , int i  , vector<int>adj[])
    {
        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 , x[k] , adj))
                    return true;
            }
            if(visiteddfs[x[k]])
            {
                return true;
            }

        }
        visiteddfs[i] = false;
        return false;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        vector<int>adj[numCourses];
        vector<bool>visited(numCourses , false);
        vector<bool>visiteddfs(numCourses , false);
        int p = prerequisites.size();
        for(int i =0 ; i < p ; i++)
        { 
            int l = prerequisites[i][0];
            int m = prerequisites[i][1];
            adj[m].push_back(l);

        }
        for(int i = 0 ; i < numCourses ; i++)
        {
            if(!visited[i])
            {
                if(dfs(visited , visiteddfs , i , adj))
                    return false;

            }

        }
        return true;
        
        
    }
};

 


Comments

Post a Comment