Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //nasarouf@cs.ubc.ca
- //topological sort
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #include <queue>
- using namespace std;
- #define MAX 1000001
- int n,seen[MAX],m,indeg[MAX];
- pair<int,int> edges[MAX],*e[MAX];
- priority_queue<int,vector<int>,greater<int> > q;
- int main() {
- int i=0,j,k;
- //input
- cin>>n;
- m=0;
- while(n--){
- cin>>k>>i; seen[i]=1;
- while(--k){
- cin>>j; seen[j]=1; indeg[j]++;
- edges[m++]=make_pair(i,j);
- i=j;
- }
- }
- sort(edges,edges+m);
- for (i=m-1; i>=0; i--) e[edges[i].first]=edges+i;
- //queue up all 0-indegree nodes. pop, add more, repeat.
- for (i=0; i<=MAX; i++) if (seen[i] && indeg[i]==0) q.push(i);
- int first=1;
- while(!q.empty()){
- if (!first) cout<<" "; first=0;
- i=q.top(); q.pop(); cout<<i;
- for(; e[i] && e[i][0].first==i; e[i]++){
- j=e[i][0].second;
- if (--indeg[j]==0) q.push(j);
- }
- }
- cout<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement