Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- typedef vector< int > vi;
- typedef vector< vi > vvi;
- void topolol(vvi& G,vi& dg,vi& topo){
- priority_queue<int, vector<int>, greater<int> > vs;
- for(int i=0;i<dg.size();++i)
- if(dg[i]==0) vs.push(i);
- int IX = 0;
- while(not vs.empty() ){
- int v = vs.top();
- vs.pop();
- topo[IX++] = v;
- for(int i=0;i<G[v].size();++i){
- int adj = G[v][i];
- --dg[adj];
- if(dg[adj]==0)
- vs.push(adj);
- }
- }
- }
- int main(){
- int n,m;
- while(cin >> n >> m){
- vvi G(n);
- vi in_dg(n,0);
- while(m--){
- int u,v;
- cin >> u >> v;
- G[u].push_back(v);
- ++in_dg[v];
- }
- vi topo(n);
- topolol(G,in_dg,topo);
- cout << topo[0];
- for(int i=1; i<topo.size(); ++i)
- cout << ' ' << topo[i];
- cout << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement