// A C++ program to find single source longest distances   // in a DAG   #include          using     namespace     std  ;   // Graph is represented using adjacency list. Every node of   // adjacency list contains vertex number of the vertex to   // which edge connects. It also contains weight of the edge   class     AdjListNode   {      int     v  ;      int     weight  ;   public  :      AdjListNode  (  int     _v       int     _w  )      {      v     =     _v  ;      weight     =     _w  ;      }      int     getV  ()      {      return     v  ;      }      int     getWeight  ()      {      return     weight  ;      }   };   // Graph class represents a directed graph using adjacency   // list representation   class     Graph   {      int     V  ;     // No. of vertices      // Pointer to an array containing adjacency lists      list   <  AdjListNode  >*     adj  ;      // This function uses DFS      void     longestPathUtil  (  int       vector   <  bool  >     &       stack   <  int  >     &  );   public  :      Graph  (  int  );     // Constructor      ~  Graph  ();     // Destructor      // function to add an edge to graph      void     addEdge  (  int       int       int  );      void     longestPath  (  int  );   };   Graph  ::  Graph  (  int     V  )     // Constructor   {      this  ->  V     =     V  ;      adj     =     new     list   <  AdjListNode  >  [  V  ];   }   Graph  ::~  Graph  ()     // Destructor   {      delete  []     adj  ;   }   void     Graph  ::  addEdge  (  int     u       int     v       int     weight  )   {      AdjListNode     node  (  v       weight  );      adj  [  u  ].  push_back  (  node  );     // Add v to u's list   }   // A recursive function used by longestPath. See below   // link for details.   // https://www.geeksforgeeks.org/dsa/topological-sorting/   void     Graph  ::  longestPathUtil  (  int     v       vector   <  bool  >     &  visited        stack   <  int  >     &  Stack  )   {      // Mark the current node as visited      visited  [  v  ]     =     true  ;      // Recur for all the vertices adjacent to this vertex      for     (  AdjListNode     node     :     adj  [  v  ])      {      if     (  !  visited  [  node  .  getV  ()])      longestPathUtil  (  node  .  getV  ()     visited       Stack  );      }      // Push current vertex to stack which stores topological      // sort      Stack  .  push  (  v  );   }   // The function do Topological Sort and finds longest   // distances from given source vertex   void     Graph  ::  longestPath  (  int     s  )   {      // Initialize distances to all vertices as infinite and      // distance to source as 0      int     dist  [  V  ];      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )      dist  [  i  ]     =     INT_MAX  ;      dist  [  s  ]     =     0  ;      stack   <  int  >     Stack  ;      // Mark all the vertices as not visited      vector   <  bool  >     visited  (  V       false  );      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )      if     (  visited  [  i  ]     ==     false  )      longestPathUtil  (  i       visited       Stack  );      // Process vertices in topological order      while     (  !  Stack  .  empty  ())      {      // Get the next vertex from topological order      int     u     =     Stack  .  top  ();      Stack  .  pop  ();      if     (  dist  [  u  ]     !=     INT_MAX  )      {      // Update distances of all adjacent vertices      // (edge from u -> v exists)      for     (  AdjListNode     v     :     adj  [  u  ])      {      // consider negative weight of edges and      // find shortest path      if     (  dist  [  v  .  getV  ()]     >     dist  [  u  ]     +     v  .  getWeight  ()     *     -1  )      dist  [  v  .  getV  ()]     =     dist  [  u  ]     +     v  .  getWeight  ()     *     -1  ;      }      }      }      // Print the calculated longest distances      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )      {      if     (  dist  [  i  ]     ==     INT_MAX  )      cout      < <     'INT_MIN '  ;      else      cout      < <     (  dist  [  i  ]     *     -1  )      < <     ' '  ;      }   }   // Driver code   int     main  ()   {      Graph     g  (  6  );      g  .  addEdge  (  0       1       5  );      g  .  addEdge  (  0       2       3  );      g  .  addEdge  (  1       3       6  );      g  .  addEdge  (  1       2       2  );      g  .  addEdge  (  2       4       4  );      g  .  addEdge  (  2       5       2  );      g  .  addEdge  (  2       3       7  );      g  .  addEdge  (  3       5       1  );      g  .  addEdge  (  3       4       -1  );      g  .  addEdge  (  4       5       -2  );      int     s     =     1  ;      cout      < <     'Following are longest distances from '       < <     'source vertex '      < <     s      < <     '   n  '  ;      g  .  longestPath  (  s  );      return     0  ;   }   

   # A Python3 program to find single source    # longest distances in a DAG   import   sys   def   addEdge  (  u     v     w  ):   global   adj   adj  [  u  ]  .  append  ([  v     w  ])   # A recursive function used by longestPath.    # See below link for details.   # https:#www.geeksforgeeks.org/topological-sorting/   def   longestPathUtil  (  v  ):   global   visited     adj    Stack   visited  [  v  ]   =   1   # Recur for all the vertices adjacent   # to this vertex   for   node   in   adj  [  v  ]:   if   (  not   visited  [  node  [  0  ]]):   longestPathUtil  (  node  [  0  ])   # Push current vertex to stack which    # stores topological sort   Stack  .  append  (  v  )   # The function do Topological Sort and finds   # longest distances from given source vertex   def   longestPath  (  s  ):   # Initialize distances to all vertices    # as infinite and   global   visited     Stack     adj    V   dist   =   [  sys  .  maxsize   for   i   in   range  (  V  )]   # for (i = 0 i  < V i++)   # dist[i] = INT_MAX   dist  [  s  ]   =   0   for   i   in   range  (  V  ):   if   (  visited  [  i  ]   ==   0  ):   longestPathUtil  (  i  )   # print(Stack)   while   (  len  (  Stack  )   >   0  ):   # Get the next vertex from topological order   u   =   Stack  [  -  1  ]   del   Stack  [  -  1  ]   if   (  dist  [  u  ]   !=   sys  .  maxsize  ):   # Update distances of all adjacent vertices   # (edge from u -> v exists)   for   v   in   adj  [  u  ]:   # Consider negative weight of edges and   # find shortest path   if   (  dist  [  v  [  0  ]]   >   dist  [  u  ]   +   v  [  1  ]   *   -  1  ):   dist  [  v  [  0  ]]   =   dist  [  u  ]   +   v  [  1  ]   *   -  1   # Print the calculated longest distances   for   i   in   range  (  V  ):   if   (  dist  [  i  ]   ==   sys  .  maxsize  ):   print  (  'INT_MIN '     end   =   ' '  )   else  :   print  (  dist  [  i  ]   *   (  -  1  )   end   =   ' '  )   # Driver code   if   __name__   ==   '__main__'  :   V   =   6   visited   =   [  0   for   i   in   range  (  7  )]   Stack   =   []   adj   =   [[]   for   i   in   range  (  7  )]   addEdge  (  0     1     5  )   addEdge  (  0     2     3  )   addEdge  (  1     3     6  )   addEdge  (  1     2     2  )   addEdge  (  2     4     4  )   addEdge  (  2     5     2  )   addEdge  (  2     3     7  )   addEdge  (  3     5     1  )   addEdge  (  3     4     -  1  )   addEdge  (  4     5     -  2  )   s   =   1   print  (  'Following are longest distances from source vertex'     s  )   longestPath  (  s  )   # This code is contributed by mohit kumar 29   

   // C# program to find single source longest distances   // in a DAG   using     System  ;   using     System.Collections.Generic  ;   // Graph is represented using adjacency list. Every node of   // adjacency list contains vertex number of the vertex to   // which edge connects. It also contains weight of the edge   class     AdjListNode     {      private     int     v  ;      private     int     weight  ;      public     AdjListNode  (  int     _v       int     _w  )      {      v     =     _v  ;      weight     =     _w  ;      }      public     int     getV  ()     {     return     v  ;     }      public     int     getWeight  ()     {     return     weight  ;     }   }   // Graph class represents a directed graph using adjacency   // list representation   class     Graph     {      private     int     V  ;     // No. of vertices      // Pointer to an array containing adjacency lists      private     List   <  AdjListNode  >  []     adj  ;      public     Graph  (  int     v  )     // Constructor      {      V     =     v  ;      adj     =     new     List   <  AdjListNode  >  [     v     ];      for     (  int     i     =     0  ;     i      <     v  ;     i  ++  )      adj  [  i  ]     =     new     List   <  AdjListNode  >  ();      }      public     void     AddEdge  (  int     u       int     v       int     weight  )      {      AdjListNode     node     =     new     AdjListNode  (  v       weight  );      adj  [  u  ].  Add  (  node  );     // Add v to u's list      }      // A recursive function used by longestPath. See below      // link for details.      // https://www.geeksforgeeks.org/dsa/topological-sorting/      private     void     LongestPathUtil  (  int     v       bool  []     visited        Stack   <  int  >     stack  )      {      // Mark the current node as visited      visited  [  v  ]     =     true  ;      // Recur for all the vertices adjacent to this      // vertex      foreach  (  AdjListNode     node     in     adj  [  v  ])      {      if     (  !  visited  [  node  .  getV  ()])      LongestPathUtil  (  node  .  getV  ()     visited        stack  );      }      // Push current vertex to stack which stores      // topological sort      stack  .  Push  (  v  );      }      // The function do Topological Sort and finds longest      // distances from given source vertex      public     void     LongestPath  (  int     s  )      {          // Initialize distances to all vertices as infinite      // and distance to source as 0      int  []     dist     =     new     int  [  V  ];      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )      dist  [  i  ]     =     Int32  .  MaxValue  ;      dist  [  s  ]     =     0  ;      Stack   <  int  >     stack     =     new     Stack   <  int  >  ();      // Mark all the vertices as not visited      bool  []     visited     =     new     bool  [  V  ];      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )     {      if     (  visited  [  i  ]     ==     false  )      LongestPathUtil  (  i       visited       stack  );      }      // Process vertices in topological order      while     (  stack  .  Count     >     0  )     {      // Get the next vertex from topological order      int     u     =     stack  .  Pop  ();      if     (  dist  [  u  ]     !=     Int32  .  MaxValue  )     {      // Update distances of all adjacent vertices      // (edge from u -> v exists)      foreach  (  AdjListNode     v     in     adj  [  u  ])      {      // consider negative weight of edges and      // find shortest path      if     (  dist  [  v  .  getV  ()]      >     dist  [  u  ]     +     v  .  getWeight  ()     *     -  1  )      dist  [  v  .  getV  ()]      =     dist  [  u  ]     +     v  .  getWeight  ()     *     -  1  ;      }      }      }      // Print the calculated longest distances      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )     {      if     (  dist  [  i  ]     ==     Int32  .  MaxValue  )      Console  .  Write  (  'INT_MIN '  );      else      Console  .  Write  (  '{0} '       dist  [  i  ]     *     -  1  );      }      Console  .  WriteLine  ();      }   }   public     class     GFG     {      // Driver code      static     void     Main  (  string  []     args  )      {      Graph     g     =     new     Graph  (  6  );      g  .  AddEdge  (  0       1       5  );      g  .  AddEdge  (  0       2       3  );      g  .  AddEdge  (  1       3       6  );      g  .  AddEdge  (  1       2       2  );      g  .  AddEdge  (  2       4       4  );      g  .  AddEdge  (  2       5       2  );      g  .  AddEdge  (  2       3       7  );      g  .  AddEdge  (  3       5       1  );      g  .  AddEdge  (  3       4       -  1  );      g  .  AddEdge  (  4       5       -  2  );      int     s     =     1  ;      Console  .  WriteLine  (      'Following are longest distances from source vertex {0} '        s  );      g  .  LongestPath  (  s  );      }   }   // This code is contributed by cavi4762.   

   // A Java program to find single source longest distances   // in a DAG   import     java.util.*  ;   // Graph is represented using adjacency list. Every   // node of adjacency list contains vertex number of   // the vertex to which edge connects. It also   // contains weight of the edge   class   AdjListNode     {      private     int     v  ;      private     int     weight  ;      AdjListNode  (  int     _v       int     _w  )      {      v     =     _v  ;      weight     =     _w  ;      }      int     getV  ()     {     return     v  ;     }      int     getWeight  ()     {     return     weight  ;     }   }   // Class to represent a graph using adjacency list   // representation   public     class   GFG     {      int     V  ;     // No. of vertices'      // Pointer to an array containing adjacency lists      ArrayList   <  AdjListNode  >[]     adj  ;      @SuppressWarnings  (  'unchecked'  )      GFG  (  int     V  )     // Constructor      {      this  .  V     =     V  ;      adj     =     new     ArrayList  [  V  ]  ;      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )     {      adj  [  i  ]     =     new     ArrayList   <>  ();      }      }      void     addEdge  (  int     u       int     v       int     weight  )      {      AdjListNode     node     =     new     AdjListNode  (  v       weight  );      adj  [  u  ]  .  add  (  node  );     // Add v to u's list      }      // A recursive function used by longestPath. See      // below link for details https://      // www.geeksforgeeks.org/topological-sorting/      void     topologicalSortUtil  (  int     v       boolean     visited  []        Stack   <  Integer  >     stack  )      {      // Mark the current node as visited      visited  [  v  ]     =     true  ;      // Recur for all the vertices adjacent to this      // vertex      for     (  int     i     =     0  ;     i      <     adj  [  v  ]  .  size  ();     i  ++  )     {      AdjListNode     node     =     adj  [  v  ]  .  get  (  i  );      if     (  !  visited  [  node  .  getV  ()  ]  )      topologicalSortUtil  (  node  .  getV  ()     visited        stack  );      }      // Push current vertex to stack which stores      // topological sort      stack  .  push  (  v  );      }      // The function to find Smallest distances from a      // given vertex. It uses recursive      // topologicalSortUtil() to get topological sorting.      void     longestPath  (  int     s  )      {      Stack   <  Integer  >     stack     =     new     Stack   <  Integer  >  ();      int     dist  []     =     new     int  [  V  ]  ;      // Mark all the vertices as not visited      boolean     visited  []     =     new     boolean  [  V  ]  ;      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )      visited  [  i  ]     =     false  ;      // Call the recursive helper function to store      // Topological Sort starting from all vertices      // one by one      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )      if     (  visited  [  i  ]     ==     false  )      topologicalSortUtil  (  i       visited       stack  );      // Initialize distances to all vertices as      // infinite and distance to source as 0      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )      dist  [  i  ]     =     Integer  .  MAX_VALUE  ;      dist  [  s  ]     =     0  ;      // Process vertices in topological order      while     (  stack  .  isEmpty  ()     ==     false  )     {      // Get the next vertex from topological      // order      int     u     =     stack  .  peek  ();      stack  .  pop  ();      // Update distances of all adjacent vertices      if     (  dist  [  u  ]     !=     Integer  .  MAX_VALUE  )     {      for     (  AdjListNode     v     :     adj  [  u  ]  )     {      if     (  dist  [  v  .  getV  ()  ]      >     dist  [  u  ]     +     v  .  getWeight  ()     *     -  1  )      dist  [  v  .  getV  ()  ]      =     dist  [  u  ]     +     v  .  getWeight  ()     *     -  1  ;      }      }      }      // Print the calculated longest distances      for     (  int     i     =     0  ;     i      <     V  ;     i  ++  )      if     (  dist  [  i  ]     ==     Integer  .  MAX_VALUE  )      System  .  out  .  print  (  'INF '  );      else      System  .  out  .  print  (  dist  [  i  ]     *     -  1     +     ' '  );      }      // Driver program to test above functions      public     static     void     main  (  String     args  []  )      {      // Create a graph given in the above diagram.      // Here vertex numbers are 0 1 2 3 4 5 with      // following mappings:      // 0=r 1=s 2=t 3=x 4=y 5=z      GFG     g     =     new     GFG  (  6  );      g  .  addEdge  (  0       1       5  );      g  .  addEdge  (  0       2       3  );      g  .  addEdge  (  1       3       6  );      g  .  addEdge  (  1       2       2  );      g  .  addEdge  (  2       4       4  );      g  .  addEdge  (  2       5       2  );      g  .  addEdge  (  2       3       7  );      g  .  addEdge  (  3       5       1  );      g  .  addEdge  (  3       4       -  1  );      g  .  addEdge  (  4       5       -  2  );      int     s     =     1  ;      System  .  out  .  print  (      'Following are longest distances from source vertex '      +     s     +     ' n'  );      g  .  longestPath  (  s  );      }   }   // This code is contributed by Prithi_Dey   

   class     AdjListNode     {      constructor  (  v       weight  )     {      this  .  v     =     v  ;      this  .  weight     =     weight  ;      }      getV  ()     {     return     this  .  v  ;     }      getWeight  ()     {     return     this  .  weight  ;     }   }   class     GFG     {      constructor  (  V  )     {      this  .  V     =     V  ;      this  .  adj     =     new     Array  (  V  );      for     (  let     i     =     0  ;     i      <     V  ;     i  ++  )     {      this  .  adj  [  i  ]     =     new     Array  ();      }      }      addEdge  (  u       v       weight  )     {      let     node     =     new     AdjListNode  (  v       weight  );      this  .  adj  [  u  ].  push  (  node  );      }      topologicalSortUtil  (  v       visited       stack  )     {      visited  [  v  ]     =     true  ;      for     (  let     i     =     0  ;     i      <     this  .  adj  [  v  ].  length  ;     i  ++  )     {      let     node     =     this  .  adj  [  v  ][  i  ];      if     (  !  visited  [  node  .  getV  ()])     {      this  .  topologicalSortUtil  (  node  .  getV  ()     visited       stack  );      }      }      stack  .  push  (  v  );      }      longestPath  (  s  )     {      let     stack     =     new     Array  ();      let     dist     =     new     Array  (  this  .  V  );      let     visited     =     new     Array  (  this  .  V  );      for     (  let     i     =     0  ;     i      <     this  .  V  ;     i  ++  )     {      visited  [  i  ]     =     false  ;      }      for     (  let     i     =     0  ;     i      <     this  .  V  ;     i  ++  )     {      if     (  !  visited  [  i  ])     {      this  .  topologicalSortUtil  (  i       visited       stack  );      }      }      for     (  let     i     =     0  ;     i      <     this  .  V  ;     i  ++  )     {      dist  [  i  ]     =     Number  .  MAX_SAFE_INTEGER  ;      }              dist  [  s  ]     =     0  ;      let     u     =     stack  .  pop  ();      while     (  stack  .  length     >     0  )     {      u     =     stack  .  pop  ();      if     (  dist  [  u  ]     !==     Number  .  MAX_SAFE_INTEGER  )     {      for     (  let     v     of     this  .  adj  [  u  ])     {      if     (  dist  [  v  .  getV  ()]     >     dist  [  u  ]     +     v  .  getWeight  ()     *     -  1  )     {      dist  [  v  .  getV  ()]     =     dist  [  u  ]     +     v  .  getWeight  ()     *     -  1  ;      }      }      }   }              for     (  let     i     =     0  ;     i      <     this  .  V  ;     i  ++  )     {      if     (  dist  [  i  ]     ===     Number  .  MAX_SAFE_INTEGER  )     {      console  .  log  (  'INF'  );      }      else     {      console  .  log  (  dist  [  i  ]     *     -  1  );      }      }      }   }   let     g     =     new     GFG  (  6  );   g  .  addEdge  (  0       1       5  );   g  .  addEdge  (  0       2       3  );   g  .  addEdge  (  1       3       6  );   g  .  addEdge  (  1       2       2  );   g  .  addEdge  (  2       4       4  );   g  .  addEdge  (  2       5       2  );   g  .  addEdge  (  2       3       7  );   g  .  addEdge  (  3       5       1  );   g  .  addEdge  (  3       4       -  1  );   g  .  addEdge  (  4       5       -  2  );   console  .  log  (  'Longest distances from the vertex 1 : '  );   g  .  longestPath  (  1  );   //this code is contributed by devendra