Problem Statement

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.

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.

Problem Link

Course Schedule - LeetCode

Code (Finding cycle in a directed graph)

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        int n = numCourses;
        
        vector<int> adj[n];
        
        for(auto p:prerequisites)
          adj[p[1]].push_back(p[0]);
        
        vector<int> visited(n,false),inStack(n,false);
        
        for(int i=0;i<n;i++)
        {
            if(!visited[i])
            {
                if(dfs(i,adj,visited,inStack))
                    **return false; // Be careful of this!!**
            }
        }
        **return true; // Be careful of this!!**
    }
    
    bool dfs(int u,vector<int> adj[],vector<int>& visited,vector<int>& inStack)
    {
        if(!visited[u])
        {
            visited[u] = true;
            inStack[u] = true;
        }
        
        for(int v:adj[u])
        {
            if(!visited[v])
            {
                if(dfs(v,adj,visited,inStack))
                    return true;
            }
            else if(inStack[v])
                return true;
        }
        inStack[u] = false;
        return false;
        
    }
};