Problem Statement

There are a total of N tasks, labelled from 0 to N-1. Given an array arr where arr[i] = [a, b] indicates that you must takes courses b first if you want to take course a. Find the order of tasks you should pick to finish all tasks.

Examples

Example 1:

Input: N = 4,
       arr = [
              [1, 0],
              [2, 1],
              [3, 2]
             ]
Output: [0, 1, 2, 3]

Explanation: First, finish task 0, as it has no prerequisites. Then, finish task 1, since it depends only on task 0. After that, finish task 2, since it depends only on task 1. Finally, finish task 3, since it depends only on task 2.

Example 2:

Input: N = 4,
       arr = [
              [0, 1],
              [3, 2],
              [1, 3],
              [3, 0]
             ]
Output: []

Explanation: It is impossible to finish all the tasks. Let's analyse it:
For pair {0, 1} -> we need to finish task 1 and then task 0 (order: 1->0).
For pair {3, 2} -> we need to finish task 2 and then task 3 (order: 2->3).
For pair {1, 3} -> we need to finish task 3 and then task 1 (order: 2->3->0).
But for pair {3, 0} -> we need to finish task 0 first and then task 3, which contradicts the previous order. So, it is not possible to finish all the tasks.

Different Approaches

1️⃣ Topological Order (BFS)

Intuition:

This problem is a continuation of the problem Course Schedule-I. Just the only difference here is that instead of determining whether the tasks can be finished or not, the problem requires us to find out the ordering of tasks so that all the tasks can be finished. If no such ordering is possible, an empty list can be returned.

Approach:

1. Using the dependencies of courses, prepare a directed graph.
2. Get the topological ordering of the graph formed.
3. If the topological ordering contains all nodes, all the courses can be completed in that order, which can be returned as an answer.
4. Otherwise, it is not possible to complete all the courses, so an empty list can be returned

Dry Run:

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:

    /* Function to return the topological
     sorting of given graph */
    vector<int> topoSort(int V, vector<int> adj[]) {
	    
        // To store the In-degrees of nodes
	    vector<int> inDegree(V, 0);
	    
	    // Update the in-degrees of nodes
		for (int i = 0; i < V; i++) {
		    
			for(auto it : adj[i]) {
			    // Update the in-degree
			    inDegree[it]++;
			}
		}
        
        // To store the result
        vector<int> ans;
	    
	    // Queue to facilitate BFS
	    queue<int> q;
	    
	    // Add the nodes with no in-degree to queue
	    for(int i=0; i<V; i++) {
	        if(inDegree[i] == 0) q.push(i);
	    }
	    
	    // Until the queue is empty
	    while(!q.empty()) {
	        
	        // Get the node
	        int node = q.front();
	        
	        // Add it to the answer
	        ans.push_back(node);
	        q.pop();
	        
	        // Traverse the neighbours
	        for(auto it : adj[node]) {
	            
	            // Decrement the in-degree
	            inDegree[it]--;
	            
	            /* Add the node to queue if 
	            its in-degree becomes zero */
	            if(inDegree[it] == 0) q.push(it);
	        }
	    }
	    
	    // Return the result
	    return ans;
    }
    
public:

	/* Function to determine order
	of tasks to finish all tasks */
	vector<int> findOrder(int N, vector<vector<int>> arr) {
        
        // To store the graph
        vector<int> adj[N];
        
        // Form the graph
        for(auto it : arr) {
            int u = it[0];
            int v = it[1];
            
            // Add the edge v-> u
            adj[v].push_back(u);
        }
        
        // Get the topological ordering of graph
        vector<int> topo = topoSort(N, adj);
        
        /* If it doesn't contain all nodes,
        it is impossible to finish all tasks */
        if(topo.size() < N) return {};
        
        // Return the ordering otherwise
        return topo;
    }
};

int main() {
    
    int N = 4;
    vector<vector<int>> arr = {
         {1,0},
         {2,1},
         {3,2}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to determine order
	of tasks to finish all tasks */
    vector<int> ans = sol.findOrder(N, arr);
    
    // Output
    cout << "The order to perform tasks is:\n";
    for(int i=0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(V+E) (where V and E represent the number of nodes and edges in the given graph)
  • Forming the graph takes O(E) time.
  • Finding topological sort takes O(V+E) time.
• Space Complexity:O(V+E)
  • Storing the graph takes O(E) space.
  • Topological sorting algorithm uses extra O(V) computational space.