15.Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

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.

Solution: (Cycle Detection in Directed Graph)

Using 3 colours/DFS

class Solution
{
public:
    bool dfs(int node, vector<int> v[], vector<int> &colr)
    {
        colr[node] = 1;
        for (int i = 0; i < v[node].size(); i++)
        {
            if (colr[v[node][i]] == 1)
            {
                return true;
            }

            if (colr[v[node][i]] == 0)
            {
                if (dfs(v[node][i], v, colr))
                {
                    return true;
                }
            }
        }
        colr[node] = 2;
        return false;
    }

    bool canFinish(int numCourses, vector<vector<int>> &prerequisites)
    {
        vector<int> v[numCourses];
        vector<int> colr(numCourses, 0);
        for (int i = 0; i < prerequisites.size(); i++)
        {
            v[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }

        for (int i = 0; i < numCourses; i++)
        {
            if (colr[i] == 0)
            {
                if (dfs(i, v, colr))
                {
                    return false;
                }
            }
        }
        return true;
    }
};

Time Complexity: O(V + E)