Minimum time taken by each job to be completed given by a Directed Acyclic Graph | Java 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
import java . util . * ; class GFG { static final int maxN = 100000 ; @ SuppressWarnings ( " unchecked " ) static Vector < Integer > [ ] graph = new Vector [ maxN ] ; static int [ ] indegree = new int [ maxN ] ; static int [ ] job = new int [ maxN ] ; static void addEdge ( int u , int v ) { graph [ u ] . add ( v ) ; indegree [ v ] ++ ; } static void printOrder ( int n , int m ) { Queue < Integer > q = new LinkedList < > ( ) ; for ( int i = 1 ; i <= n ; i ++ ) { if ( indegree [ i ] == 0 ) { q . add ( i ) ; job [ i ] = 1 ; } } while ( ! q . isEmpty ( ) ) { int cur = q . peek ( ) ; q . remove ( ) ; for ( int adj : graph [ cur ] ) { indegree [ adj ] -- ; if ( indegree [ adj ] == 0 ) { job [ adj ] = 1 + job [ cur ] ; q . add ( adj ) ; } } } for ( int i = 1 ; i <= n ; i ++ ) System . out . print ( job [ i ] + " ▁ " ) ; System . out . print ( "NEW_LINE"); } public static void main ( String [ ] args ) { int n , m ; n = 10 ; m = 13 ; for ( int i = 0 ; i < graph . length ; i ++ ) graph [ i ] = new Vector < Integer > ( ) ; 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 ) ; } }