[CF825E] Minimal Labels（反向建图，拓扑排序）

题目链接：http://codeforces.com/problemset/problem/825/E

题意：给一个有向图，求一个排列，这个排列是每一个点的序号，使得序号对应的点的排序符合拓扑序并且这个排列字典序最小。

直接跑字典序最小的拓扑排序是不行的，因为那样只是确保点的字典序而非这个排列的字典序，比如这个数据：

10 1
5 2

反过来考虑，点号大的入度为0的点一定排在后面，这个位置确定了。但是点好小的入度为0的未必一定排在前面，因为这个点之前可能有入度不为0，但是与此点无关的点在前面，按题意这种点是要比当前点的序号小的。

反向建图，跑字典序最大的拓扑排序就行了。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100100;
int n, m, cnt;
vector<int> G[maxn];
int ret[maxn], in[maxn];
priority_queue<int> pq;

void init() {
    cnt = n;
    memset(in, 0, sizeof(in));
    while(!pq.empty()) pq.pop();
    for(int i = 0; i < maxn; i++) G[i].clear();
}

signed main() {
    // freopen("in", "r", stdin);
    int u, v;
    while(~scanf("%d%d",&n,&m)) {
        init();
        for(int i = 0; i < m; i++) {
            scanf("%d%d",&u,&v);
            G[v].push_back(u);
            in[u]++;
        }
        for(int i = 1; i <= n; i++) {
            if(!in[i]) pq.push(i);
        }
        while(!pq.empty()) {
            int u = pq.top(); pq.pop();
            ret[u] = cnt--;
            for(auto v : G[u]) {
                in[v]--;
                if(in[v] == 0) pq.push(v);
            }
        }
        for(int i = 1; i <= n; i++) {
            printf("%d%c", ret[i], i==n?'
':' ');
        }
    }
    return 0;
}