fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  //priority_queue<int,vector<int>,greater<int>>q;
  4. vector<int> topo(int V, vector<vector<int>>& adj )
  5. {
  6.     vector<int> indegree(V, 0);
  7.  
  8.     for(int i = 0; i < V; i++)
  9.         for(int v : adj[i])
  10.             indegree[v]++;
  11.  
  12.   //  priority_queue<int,vector<int>,greater<int>>q;
  13.   // priority queue pair<int,int>
  14.       queue<int>q;
  15.  
  16.     for(int i = 0; i < V; i++)
  17.         if(indegree[i] == 0)
  18.             q.push(i);
  19.  
  20.     vector<int> result;
  21.  
  22.     while(!q.empty())
  23.     {
  24.        // int u = q.top();
  25.        int u=q.front();
  26.         q.pop();
  27.  
  28.         result.push_back(u);
  29.  
  30.         for(int v : adj[u])
  31.         {
  32.             indegree[v]--;
  33.             if(indegree[v] == 0)
  34.                 q.push(v);
  35.         }
  36.     }
  37.  
  38.     if(result.size() != V) // cyc
  39.         return {};
  40.  
  41.     return result;
  42. }
  43.  
  44. int main()
  45. {
  46.     int V, E;
  47.     cin >> V >> E;
  48.     vector<vector<int>> adj(V);
  49.      //priority_queue<int,vector<int>,greater<int>>q;
  50.     for(int i=0;i<V;i++)
  51.     {
  52.         int x;
  53.         cin >> x;
  54.    //    q.push(x);
  55.     }
  56.     for(int i = 0; i < E; i++)
  57.     {
  58.         int u, v;
  59.         cin >> u >> v;
  60.         u--;
  61.         v--;
  62.         adj[u].push_back(v);
  63.     }
  64.     vector<int>result=topo(V,adj);
  65.       for(int  x:result)
  66.       {
  67.           cout<<x+1<<" ";
  68.       }
  69.  
  70. }
  71. /*
  72. 5 4
  73. 10 7 6 1 4
  74. 5 1
  75. 4 5
  76. 2 5
  77. 3 4
  78. */
  79. /*
  80.  
  81. */
  82.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vL2ydE
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!