Leetcode Study Day 44

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

I found this solution from Leetcode. Here is his explanation:

We just have to find if our graph contains cycle or not because if graph contains cycle then all tnodes in cycle are interdependent and 1 course cannot be completed because its prerequisite is dependent on other course and it goes on .
We used coloring algorithm to find if there is cycle in graph or not.

Coloring Algorithm

vis[id]=0 is used for node which is not yet visited, vis[id]=1 is used for the node which is visited and currently its child nodes are being visited and vis[id]=2 done when all the child nodes of a node (“id”) are visited and the function returns to parent node of node (“id”). So at that time it is marked as 2 because this node does not require any further traversing.

class Solution {
public:
    bool iscycle(vector<int> adj[],vector<int> &vis,int id){
        // if we find this node again, we can make sure it's a cycle
        if(vis[id]==1)
            return true;
        // if it's a new node
        if(vis[id]==0){
            // we set it as 1
            vis[id]=1;
            // we check all its adjacent nodes
            for(int edge : adj[id]){
                if(iscycle(adj,vis,edge))
                    return true;
            }
        }
        vis[id] = 2;
        return false;
    }
    bool canFinish(int n, vector<vector<int>>& pre) {
        // a vector with n elements, each element is a vector
        vector<int> adj[n];
        for(auto edge : pre)
            // push the pre[2]th number with course pre[1]
            adj[edge[1]].push_back(edge[0]);
        // a vector with n elements, each element is 0
        vector<int> vis(n,0);
        
        for(int i=0;i<n;i++){
            // if we find a cycle, return false
            if(iscycle(adj,vis,i))
                return false;
        }
        return true;
    }
};