Leetcode 207. Course Schedule [Medium]

Problem:

source: course-schedule

Identify problem

Given the number of courses that needs to be take and their pre-requisite relationship given in forms of vector pair we have to identify whehter we could complete the course or not.

Approaches

From the given pre-requisite relationship we could form a graph relationship as following.

in this diagram 0 is pre-requisite of 1.

So we have graphs that are pointing to their pre-requisites. How can we use this to determine whether we could complete the course?

We will be using either dfs, or bfs to traverse through the graph. If cycle exists within the graph, then we won’t be able to complete the courses returning false.

Code

1. map each course to the pre-requisites. it will look like {(key)course: (value)[pre-req1, pre-req2]}.
2. for each course in the map, move to their pre-req key until you reach course with empty list of pre-requisite course. (using bfs)
3. As you retrieve back we erase the pre-req that has been visited.
4. In order to detect cycles we need to keep track of courses that been visited for each dfs.
5. the graph could be disconnected thus we need to conduct dfs for all the courses [0, numCourses -1].

   class Solution {
   public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
           
        unordered_map<int, vector<int>> course2pre;
           
        for(int i=0; i<prerequisites.size(); ++i)
        {
            course2pre[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
           
        unordered_set<int> visited;
        for(int i=0; i<numCourses; ++i)
        {
            if(!dfs(i, course2pre, visited))
            {
                return false;
            }
        }
        return true;
    }
       
       
    bool dfs(int course, unordered_map<int, vector<int>>& course2pre, unordered_set<int>& visited)
    {
        if(visited.find(course) != visited.end())
        {
            return false;
        }
           
        if(course2pre[course].empty())
        {
            return true;
        }
           
        visited.insert(course);
   
        for(int i=0; i<course2pre[course].size(); ++i)
        {
            int nextCourse = course2pre[course][i];
               
            if(!dfs(nextCourse, course2pre, visited))
            {
                return false;
            }
        }
   
        course2pre[course].clear();
        visited.erase(course);
        return true;
    }
   };
   

Notes

• We could also use kahn’s algorithm
• leetcode 210 - course schedule II is similar question that uses topological sort.