Graph: Given course with prerequisites, find the order of taking the courses

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.

You need to find the ordering of the courses should be taken to complete all the courses.

If there are multiple solutions, return any of them.

If it is not possible, return empty array.

Example:

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

Solution Explanation:

Construct adjacency matrix.

1 → 0
2 → 0
3 → 1
3 → 2

Then call the dfs function to check for cycle and if there is a cycle, return empty array.

Else perform DFS and store the result.

Start from 0 -> no prerequisites  ->  push 0.
Course 1  ->  needs 0  ->  push 1.
Course 2  ->  needs 0  ->  push 2.
Course 3  ->  needs 1 and 2  ->  push 3.

Time Complexity: O(v+e)
Space Complexity: O(v+e)

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, vector<int>& result)
{
    visited[node]=1;
    for(int i=0;i<graph[node].size();i++)
    {
        if(visited[graph[node][i]]==1)
        	return false; 

        if(visited[graph[node][i]]==0)
        {
            if(!dfs(graph[node][i],graph,visited,result)) 
                return false;
        }
    }

    visited[node] = 2; 

    result.push_back(node); 

    return true;
}

vector<int> solution(int numCourses, vector<vector<int>>& prerequisites) 
{
    vector<vector<int>> graph(numCourses);
    for(int i=0;i<prerequisites.size();i++)
    {
        graph[prerequisites[i][0]].push_back(prerequisites[i][1]); 
    }
    vector<int> visited(numCourses,0);  

    vector<int> result; 

    bool flag = true; 
    for(int i=0;i<numCourses;i++)
    {
        if(visited[i]==0)
        {
            if(!dfs(i,graph,visited,result))
            {
                flag = false; 
                break;
            }
        }
    }

    if(!flag)
        return vector<int>();

    return result;
}

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

    vector<int> order = solution(n, prerequisites);

        for (int course : order) {
            cout << course << " ";
        }
        cout << endl;

    return 0;
}

Output

0 1 2 3