Advertisement
Guest User

Untitled

a guest
Jul 4th, 2015
382
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. typedef vector< int > vi;
  6. typedef vector< vi > vvi;
  7.  
  8. void topolol(vvi& G,vi& dg,vi& topo){
  9.     priority_queue<int, vector<int>, greater<int> > vs;
  10.     for(int i=0;i<dg.size();++i)
  11.         if(dg[i]==0) vs.push(i);
  12.     int IX = 0;
  13.     while(not vs.empty() ){
  14.         int v = vs.top();
  15.         vs.pop();
  16.         topo[IX++] = v;
  17.         for(int i=0;i<G[v].size();++i){
  18.             int adj = G[v][i];
  19.             --dg[adj];
  20.             if(dg[adj]==0)
  21.                 vs.push(adj);
  22.         }
  23.     }
  24. }
  25.  
  26. int main(){
  27.     int n,m;
  28.     while(cin >> n >> m){
  29.         vvi G(n);
  30.         vi in_dg(n,0);
  31.         while(m--){
  32.             int u,v;
  33.             cin >> u >> v;
  34.             G[u].push_back(v);
  35.             ++in_dg[v];
  36.         }
  37.         vi topo(n);
  38.         topolol(G,in_dg,topo);
  39.         cout << topo[0];
  40.         for(int i=1; i<topo.size(); ++i)
  41.             cout << ' ' << topo[i];
  42.         cout << endl;
  43.     }
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement