Topological sort

//[email protected]
//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;
}