Check if it is possible to finish all task from given dependencies using Topological Sort

Check if it is possible to finish all task from given dependencies using DFS:

If we perform a topological sort and all the nodes get visited, then it means there is no cycle and it is possible to finish all the tasks. If any of the node is unvisited, it means that particular node is dependent on another node which in turn is dependent on some other node and so on. So, we cannot finish those tasks because of circular dependency.

Step by step approach:

Calculate the indegree of all the nodes of the graph.
Start by pushing all the nodes with indegree 0 into a queue and start traversing by popping elements from the queue.
Whenever we pop a node, we decrease indegree of all its neighboring nodes by 1 and if indegree of any of the neighboring nodes becomes 0, then we push that neighboring node into our queue.
Continue the above steps till our queue becomes empty.
Now, check if all the nodes are visited. If yes, return true, else return false.

Below is the implementation of the above approach:

C++

// A BFS based solution to check if we can finish
// all tasks or not. This solution is mainly based
// on Kahn's algorithm.
#include <bits/stdc++.h>
using namespace std;
 
// Main function to check whether possible to
// finish all tasks or not
bool canFinish(int numTasks,
               vector<pair<int, int> >& prerequisites)
{
    vector<vector<int> > graph(numTasks);
    // vector to store the indegree of nodes
    vector<int> inDegree(numTasks, 0);
    // construct the graph and initialize the
    // indegree of nodes
    for (auto edge : prerequisites) {
        graph[edge.first].push_back(edge.second);
        inDegree[edge.second] += 1;
    }
    queue<int> q;
    // Push all the nodes with no dependencies
    // (indegree = 0)
    for (int i = 0; i < numTasks; i++) {
        if (!inDegree[i]) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        // reduce the indegree of all neighbors by 1
        for (int child : graph[node]) {
            inDegree[child] -= 1;
            // Push the neighboring node if we have covered
            // all its dependencies (indegree = 0)
            if (!inDegree[child])
                q.push(child);
        }
    }
    // Check if there is a node whose indegree is not zero
    for (int i = 0; i < numTasks; i++) {
        if (inDegree[i])
            return false;
    }
    return true;
}
 
int main()
{
    int numTasks = 4;
    vector<pair<int, int> > prerequisites;
    prerequisites.push_back(make_pair(1, 0));
    prerequisites.push_back(make_pair(2, 1));
    prerequisites.push_back(make_pair(3, 2));
    if (canFinish(numTasks, prerequisites)) {
        cout << "Possible to finish all tasks";
    }
    else {
        cout << "Impossible to finish all tasks";
    }
 
    return 0;
}

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
class Solution {
    // Main function to check whether it's possible to
    // finish all tasks or not
    public boolean canFinish(int numTasks,
                             int[][] prerequisites)
    {
        ArrayList<ArrayList<Integer> > graph
            = new ArrayList<>(numTasks);
        int[] inDegree = new int[numTasks];
 
        for (int i = 0; i < numTasks; i++) {
            graph.add(new ArrayList<>());
        }
 
        // Initialize the graph and in-degrees
        for (int[] edge : prerequisites) {
            graph.get(edge[0]).add(edge[1]);
            inDegree[edge[1]]++;
        }
 
        Queue<Integer> queue = new LinkedList<>();
 
        // Push all the nodes with no dependencies
        // (in-degree = 0) into the queue
        for (int i = 0; i < numTasks; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
 
        while (!queue.isEmpty()) {
            int node = queue.poll();
 
            // Reduce the in-degree of all neighbors by 1
            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--;
 
                // Push the neighboring node if we have
                // covered all its dependencies (in-degree =
                // 0)
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }
 
        // Check if there is a node whose in-degree is not
        // zero
        for (int i = 0; i < numTasks; i++) {
            if (inDegree[i] != 0) {
                return false;
            }
        }
 
        return true;
    }
 
    public static void main(String[] args)
    {
        int numTasks = 4;
        int[][] prerequisites
            = { { 1, 0 }, { 2, 1 }, { 3, 2 } };
 
        Solution solution = new Solution();
        if (solution.canFinish(numTasks, prerequisites)) {
            System.out.println(
                "Possible to finish all tasks");
        }
        else {
            System.out.println(
                "Impossible to finish all tasks");
        }
    }
}

C#

using System;
using System.Collections.Generic;
 
class Program
{
    // Main function to check whether it is possible to
    // finish all tasks or not
    static bool CanFinish(int numTasks, List<Tuple<int, int>> prerequisites)
    {
        // Create a graph represented as an adjacency list
        List<List<int>> graph = new List<List<int>>(numTasks);
        for (int i = 0; i < numTasks; i++)
        {
            graph.Add(new List<int>());
        }
 
        // Array to store the indegree of nodes
        int[] inDegree = new int[numTasks];
 
        // Construct the graph and initialize the indegree of nodes
        foreach (var edge in prerequisites)
        {
            graph[edge.Item1].Add(edge.Item2);
            inDegree[edge.Item2]++;
        }
 
        // Queue to perform BFS
        Queue<int> queue = new Queue<int>();
 
        // Push all the nodes with no dependencies (indegree = 0)
        for (int i = 0; i < numTasks; i++)
        {
            if (inDegree[i] == 0)
            {
                queue.Enqueue(i);
            }
        }
 
        // Perform BFS
        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
 
            // Reduce the indegree of all neighbors by 1
            foreach (int neighbor in graph[node])
            {
                inDegree[neighbor]--;
 
                // Enqueue the neighboring node if we have covered
                // all its dependencies (indegree = 0)
                if (inDegree[neighbor] == 0)
                {
                    queue.Enqueue(neighbor);
                }
            }
        }
 
        // Check if there is a node whose indegree is not zero
        for (int i = 0; i < numTasks; i++)
        {
            if (inDegree[i] > 0)
            {
                return false;
            }
        }
 
        return true;
    }
 
    static void Main()
    {
        int numTasks = 4;
        List<Tuple<int, int>> prerequisites = new List<Tuple<int, int>>();
        prerequisites.Add(new Tuple<int, int>(1, 0));
        prerequisites.Add(new Tuple<int, int>(2, 1));
        prerequisites.Add(new Tuple<int, int>(3, 2));
 
        if (CanFinish(numTasks, prerequisites))
        {
            Console.WriteLine("Possible to finish all tasks");
        }
        else
        {
            Console.WriteLine("Impossible to finish all tasks");
        }
    }
}

Javascript

function canFinish(numTasks, prerequisites) {
    const graph = new Array(numTasks).fill().map(() => []);
    const inDegree = new Array(numTasks).fill(0);
 
    // Construct the graph and initialize the indegree of nodes
    prerequisites.forEach((edge) => {
        graph[edge[0]].push(edge[1]);
        inDegree[edge[1]] += 1;
    });
 
    const q = [];
 
    // Push all the nodes with no dependencies (indegree = 0)
    for (let i = 0; i < numTasks; i++) {
        if (inDegree[i] === 0) {
            q.push(i);
        }
    }
 
    while (q.length > 0) {
        const node = q.shift();
 
        // Reduce the indegree of all neighbors by 1
        for (const child of graph[node]) {
            inDegree[child] -= 1;
 
            // Push the neighboring node if we have covered
            // all its dependencies (indegree = 0)
            if (inDegree[child] === 0) {
                q.push(child);
            }
        }
    }
 
    // Check if there is a node whose indegree is not zero
    for (let i = 0; i < numTasks; i++) {
        if (inDegree[i] !== 0) {
            return false;
        }
    }
 
    return true;
}
 
// Main program
const numTasks = 4;
const prerequisites = [
    [1, 0],
    [2, 1],
    [3, 2]
];
 
if (canFinish(numTasks, prerequisites)) {
    console.log("Possible to finish all tasks");
} else {
    console.log("Impossible to finish all tasks");
}

Python3

from collections import deque
 
 
class Solution:
    # Main function to check whether it's 
    # possible to finish all tasks or not
    def canFinish(self, numTasks, prerequisites):
        graph = [[] for _ in range(numTasks)]
        inDegree = [0] * numTasks
 
        # Initialize the graph and in-degrees
        for edge in prerequisites:
            graph[edge[0]].append(edge[1])
            inDegree[edge[1]] += 1
 
        queue = deque()
 
        # Push all the nodes with no dependencies 
        # (in-degree = 0) into the queue
        for i in range(numTasks):
            if inDegree[i] == 0:
                queue.append(i)
 
        while queue:
            node = queue.popleft()
 
            # Reduce the in-degree of all neighbors by 1
            for neighbor in graph[node]:
                inDegree[neighbor] -= 1
 
                # Push the neighboring node if we have 
                # covered all its dependencies (in-degree = 0)
                if inDegree[neighbor] == 0:
                    queue.append(neighbor)
 
        # Check if there is a node whose in-degree is not zero
        for i in range(numTasks):
            if inDegree[i] != 0:
                return False
 
        return True
 
 
# Test the function
numTasks = 4
prerequisites = [
    [1, 0],
    [2, 1],
    [3, 2]
]
 
solution = Solution()
if solution.canFinish(numTasks, prerequisites):
    print("Possible to finish all tasks")
else:
    print("Impossible to finish all tasks")

Output

Possible to finish all tasks

Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V)

Check if it is possible to finish all task from given dependencies (Course Schedule I)

There are a total of N tasks, labeled from 0 to N-1. Some tasks may have prerequisites, for example to do task 0 you have to first complete task 1, which is expressed as a pair: [0, 1]. Given the total number of tasks N and a list of prerequisite pairs P, find if it is possible to finish all tasks.

Examples:

Input: N = 4, P = 3, prerequisites = {{1,0},{2,1},{3,2}}
Output: Yes
Explanation: To do task 1 you should have completed task 0, and to do task 2 you should have finished task 1, and to do task 3 you should have finished task 2. So it is possible.

Input: N = 2, P = 2, prerequisites = {{1,0},{0,1}}
Output: No
Explanation: To do task 1 you should have completed task 0, and to do task 0 you should have finished task 1. So it is impossible.

Asked In: Google, Twitter, Amazon and many more companies.

Solution:

We can consider this problem as a graph (related to topological sorting) problem. All tasks are nodes of the graph and if task u is a prerequisite of task v, we will add a directed edge from node u to node v. Now, this problem is equivalent to detecting a cycle in the graph represented by prerequisites. If there is a cycle in the graph, then it is not possible to finish all tasks (because in that case there is no any topological order of tasks). Both BFS and DFS can be used to solve it.

Since pair is inconvenient for the implementation of graph algorithms, we first transform it to a graph. If task u is a prerequisite of task v, we will add a directed edge from node u to node v.

Prerequisite: Detect Cycle in a Directed Graph

Tags:

#BFS #DFS #graph-cycle #Technical Scripter 2018 #Topological Sorting #DSA #Graph #Technical Scripter #BFS #DFS #Graph