Minimum time taken by each job to be completed given by a Directed Acyclic Graph | C ++ program for the above approach ; Adjacency List to store the graph ; Array to store the in - degree of node ; Array to store the time in which the job i can be done ; Function to add directed edge between two vertices ; Insert edge from u to v ; Increasing the indegree of vertex v ; Function to find the minimum time needed by each node to get the task ; Queue to store the nodes while processing ; Update the time of the jobs who don 't require any job to  be completed before this job ; Iterate until queue is empty ; Get front element of queue ; Pop the front element ; Decrease in - degree of the current node ; Push its adjacent elements ; Print the time to complete the job ; Driver Code ; Given Nodes N and edges M ; Given Directed Edges of graph ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define maxN  100000 NEW_LINE vector < int > graph [ maxN ] ; int indegree [ maxN ] ; int job [ maxN ] ; void addEdge ( int u , int v ) { graph [ u ] . push_back ( v ) ; indegree [ v ] ++ ; } void printOrder ( int n , int m ) { queue < int > q ; for ( int i = 1 ; i <= n ; i ++ ) { if ( indegree [ i ] == 0 ) { q . push ( i ) ; job [ i ] = 1 ; } } while ( ! q . empty ( ) ) { int cur = q . front ( ) ; q . pop ( ) ; for ( int adj : graph [ cur ] ) { indegree [ adj ] -- ; if ( indegree [ adj ] == 0 ) { job [ adj ] = job [ cur ] + 1 ; q . push ( adj ) ; } } } for ( int i = 1 ; i <= n ; i ++ ) cout << job [ i ] << " ▁ " ; cout << " STRNEWLINE " ; } int main ( ) { int n , m ; n = 10 ; m = 13 ; addEdge ( 1 , 3 ) ; addEdge ( 1 , 4 ) ; addEdge ( 1 , 5 ) ; addEdge ( 2 , 3 ) ; addEdge ( 2 , 8 ) ; addEdge ( 2 , 9 ) ; addEdge ( 3 , 6 ) ; addEdge ( 4 , 6 ) ; addEdge ( 4 , 8 ) ; addEdge ( 5 , 8 ) ; addEdge ( 6 , 7 ) ; addEdge ( 7 , 8 ) ; addEdge ( 8 , 10 ) ; printOrder ( n , m ) ; return 0 ; }