Advertisement
ekanshlohiya98

MIN time all jobs dag

Jun 27th, 2022
935
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // C++ program for the above approach
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define maxN 100000
  5.  
  6. // Adjacency List to store the graph
  7. vector<int> graph[maxN];
  8.  
  9. // Array to store the in-degree of node
  10. int indegree[maxN];
  11.  
  12. // Array to store the time in which
  13. // the job i can be done
  14. int job[maxN];
  15.  
  16. // Function to add directed edge
  17. // between two vertices
  18. void addEdge(int u, int v)
  19. {
  20.     // Insert edge from u to v
  21.     graph[u].push_back(v);
  22.  
  23.     // Increasing the indegree
  24.     // of vertex v
  25.     indegree[v]++;
  26. }
  27.  
  28. // Function to find the minimum time
  29. // needed by each node to get the task
  30. void topo(int vis[],int i,stack<int> &s){
  31.     vis[i]=1;
  32.     for(auto it:graph[i]){
  33.         if(!vis[it])
  34.         topo(vis,it,s);
  35.     }
  36.     s.push(i);
  37. }
  38. void printOrder(int n, int m)
  39. {
  40.     int vis[n+1];
  41.     stack<int>s;
  42.     memset(vis,0,sizeof vis);
  43.     for(int i=1; i<=n; i++){
  44.         if(!vis[i])
  45.             topo(vis,i,s);
  46.     }
  47.     int time[n+1];
  48.     for(int i=0; i<=n; i++)
  49.     time[i]=0;
  50.     for(int i=1;i<=n;i++) {if(indegree[i]==0) time[i]=1;}
  51.    while(!s.empty()){
  52.         int node=s.top();
  53.         s.pop();
  54.         for(auto it:graph[node]){
  55.            time[it]=max(time[it],time[node]+1);
  56.         }
  57.     }
  58.     for(int i=1; i<=n; i++){
  59.         cout<<time[i]<<" ";
  60.     }
  61.  
  62.  
  63. }
  64.  
  65. // Driver Code
  66. int main()
  67. {
  68.     // Given Nodes N and edges M
  69.     int n, m;
  70.     n = 10;
  71.     m = 13;
  72.  
  73.     // Given Directed Edges of graph
  74.     addEdge(1, 3);
  75.     addEdge(1, 4);
  76.     addEdge(1, 5);
  77.     addEdge(2, 3);
  78.     addEdge(2, 8);
  79.     addEdge(2, 9);
  80.     addEdge(3, 6);
  81.     addEdge(4, 6);
  82.     addEdge(4, 8);
  83.     addEdge(5, 8);
  84.     addEdge(6, 7);
  85.     addEdge(7, 8);
  86.     addEdge(8, 10);
  87.  
  88.     // Function Call
  89.     printOrder(n, m);
  90.     return 0;
  91. }
  92.  
Advertisement
RAW Paste Data Copied
Advertisement