CSUSTOJ 题目序号配给 (拓扑排序)

题目1033

其实就是一个用优先队列求拓扑序的题，不明白的请自己去学习拓扑排序，按照队列+节点度搞。

ll r[1000009];
ll c[1000009];
priority_queue<ll,vector<ll>,greater<ll> >q;
ll k=0;
ll head[1000009];
struct pe
{ll v,next;} a[1000009];
void add(ll u,ll v)
{a[++k].next=head[u];a[k].v=v;head[u]=k;
}
ll ans[1111111];
ll op=0;
signed main()
{ll n,m;read(n);read(m);for(int i=1; i<=m; i++){ll u,v;read(u);read(v);add(u,v);c[u]++;r[v]++;}for(int i=1; i<=n; i++){if(r[i]==0){q.push(i);}}while(q.size()){ll u=q.top();ans[u]=++op;q.pop();for(int i=head[u]; i; i=a[i].next){ll v=a[i].v;r[v]--;if(r[v]==0){q.push(v);}}}for(int i=1; i<=n; i++){printf("%lld ",ans[i]);}
}