Graph: Check if the given courses can be completed with prerequisites

Problem Statement:

You are given n courses, labeled from 0 to n-1 and prerequisites[][].

prerequisites[i] = [x, y], meaning you should take course y before taking course x.

Return true if it is possible to complete all courses, other wise return failure.

Example:

Input: n = 4, prerequisites[][] = [[2, 0], [2, 1], [3, 2]]
Output: true

Explanation:

To take course 2, you have to complete course 0 and 1.

To take course 3, you should complete course 2.

All courses can be completed in order 1, 0, 2, 3

Solution Explanation:

For the solution, we need to check if the graph has a cycle or not.

Create a graph that has adjacency list as “course => Prerequisites Courses”

Then for each node in DSF, call the visited array.

If vis[i] = 2, then there is no cycle in this path, return true.
If vis[i] = 1, then there is a cycle in this path, return false.
If vis[i] = 2, then there is no cycle in this path, it is a unvisited node.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


bool dfs(int node, vector<vector<int>>&graph, vector<int>&visited)
{
    visited[node] = 1;
    
    
    for(int j=0;j<graph[node].size();j++)
    {
        if(visited[graph[node][j]]==1) 
        	return false;
        
        if(visited[graph[node][j]]==0)
            if(!dfs(graph[node][j],graph,visited)) 
            	return false;
    }
    
    visited[node] = 2;
    
    return true;
}

bool solution(int numCourses, vector<vector<int>>& prerequisites) 
{
    
    // create a graph for each course to prerequisites
    vector<vector<int>>graph(numCourses);
    
    // create a visited array to keep track of each node
    vector<int>visited(numCourses,0);
    
    // add into the graph
    for(int i=0; i<prerequisites.size(); i++)
        graph[prerequisites[i][0]].push_back(prerequisites[i][1]);
    
    // run DSF on each node
    for(int i=0;i<numCourses;i++)
    {
        if(visited[i] == 0)
            if(!dfs(i, graph, visited))
            	return false; 
    }
        
    return true;
}

int main() 
{
    int n = 4;
    vector<vector<int>> prerequisites = { {2, 0}, {2, 1}, {3, 2} };

    cout << (solution(n, prerequisites) ? "True" : "False") << endl;

    return 0;
}

Output

True