Problem Statement

There are a total of N tasks, labelled from 0 to N-1. Given an arr where arr[i] = [a, b] indicates that you must take course b first if you want to take course a. Find if it is possible to finish all tasks.

Examples

Example 1:

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

Explanation: It is possible to finish all the tasks in the order: 0 1 2 3.
First, we will finish task 0. Then we will finish task 1, task 2, and task 3.

Example 2:

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

Explanation: It is impossible to finish all the tasks. Let's analyze the pairs:
For pair {0, 1} -> we need to finish task 1 first and then task 0. {order: 1 0}.
For pair {3, 2} -> we need to finish task 2 first and then task 3. {order: 2 3}.
For pair {1, 3} -> we need to finish task 3 first and then task 1. {order: 3 1}.
For pair {3, 0} -> we need to finish task 0 first and then task 3 but task 0 requires task 1 and task 1 requires task 3. So, it is not possible to finish all the tasks.

Different Approaches

1️⃣ Topological Order (BFS)

Intuition:

How this problem can be identified as a Graph problem?

The problem suggests that some courses must be completed before other courses. This is analogous to Topological Sort Algorithm in graph which helps to find a ordering where a node must come come before other nodes in the ordering.
Hence, the courses can be represented as nodes of graphs and dependencies of courses can be shown as edges.

Now, For the graph formed, if the Topological sort can be found containing all the nodes (courses), all the courses can be completed in the order returned by topological sort. Else it is not possible to complete all the courses.

How to form the graph?

The pair [a,b] represents that the Course b must be completed before Course a.
Hence in the graph, two nodes representing Course a and b can be created with a directed edge from Node b to Node a. This way the topological sort will return Node b before Node a.

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.
4. Otherwise, it is not possible to completed all the courses.

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 if all 
	the tasks can be finished */
	bool canFinish(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, return false */
        if(topo.size() < N) return false;
        
        // Return true otherwise
        return true;
    }
};

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 if 
	all the tasks can be finished */
    bool ans = sol.canFinish(N, arr);
    
    // Output
    if(ans) 
        cout << "All the tasks can be finished.";
    else 
        cout << "All the tasks can not be finished.";
    
    return 0;
}

Complexity Analysis:

Let's denote:

N as the number of courses (nodes).

M as the number of prerequisite pairs (edges).

• Time Complexity:
  • Building the Adjacency List:
    • The loop runs over each prerequisite pair, so it takes O(M) time.
  • Computing the In-Degree Array:
    • Iterating over all nodes: O(N).
    • For each node, iterating over its neighbors: collectively O(M) (each edge is visited once).
    • Total for this step: O(N + M).
  • Initializing the Queue:
    • The loop checks each node's in-degree: O(N).
  • Kahn's Algorithm (Processing the Queue):
    • Every node is processed exactly once: O(N).
    • For each node, each outgoing edge is considered: O(M).
    • Total for this step: O(N + M).
  • Overall Time Complexity:
    • Summing up all the steps gives us O(M) + O(N + M) + O(N) + O(N + M) = O(N + M).
• Space Complexity:
  • Adjacency List:
    • Requires storage for all nodes and edges: O(N + M).
  • In-Degree Array:
    • Stores an integer for each node: O(N).
  • Queue:
    • In the worst case, might store all nodes: O(N).
  • Result Vector:
    • Stores the ordering of nodes: O(N).
  • Overall Space Complexity:
    • The total space required is O(N + M).