题解：CF825E Minimal Labels

· · 题解

题意：给你一个图，让你求一个字典序最小的排列 a 满足如果图上有从 u 到 v 的边，那么 a_u < a_v。

这道题可以用拓扑排序和贪心做，为了让字典序最小，一个错误的思路就是在拓扑排序时使用大根堆，先处理小的元素。但是有一个问题就是如果一个编号很大的点后面跟着一个编号很小的那么编号小的那个就会被最后处理。一个解决方案就是建反图并使用大根堆，让 a_u 从 n 到 1 赋值，于是编号小的就会最后赋值，达到字典序最小的效果。

代码

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

int n, m, u, v, num, a[100010], d[100010];
vector<int> g[100010];
priority_queue<int> q;
signed main() {
  cin >> n >> m;
  while (m--) {
    cin >> u >> v;
    g[v].push_back(u);
    d[u]++;
  }
  for (int i = 1; i <= n; i++)
    if (!d[i])
      q.push(i);
  num = n;
  while (!q.empty()) {
    u = q.top();
    q.pop();
    a[u] = num--;
    for (int v : g[u])
      if (!--d[v])
        q.push(v);
  }
  for (int i = 1; i <= n; i++)
    cout << a[i] << " \n"[i == n];
  return 0;
}