hexo-blog/source/_posts/oi/minimal-labels.md

---

title: Minimal Labels tags:

• Priority Queue
• Topological-Sort id: "1203" categories:
• [OI, Data Structure]
• [OI, Graph Theory] date: 2017-07-17 20:20:03 ---

题目描述

You are given a directed acyclic graph with $n$ vertices and $m$ edges. There are no self-loops or multiple edges between any pair of vertices. Graph can be disconnected.

You should assign labels to all vertices in such a way that:

• Labels form a valid permutation of length $n$ - an integer sequence such that each integer from $1$ to $n$ appears exactly once in it.
• If there exists an edge from vertex $v$ to vertex $u$ then $label_v$ should be smaller than $label_u$.
• Permutation should be lexicographically smallest among all suitable.

Find such sequence of labels to satisfy all the conditions.

题意概述

给定一张$n$个点$m$条边的有向无环图。现要将图中所有点标号。如果点$u$有一条连向点$v$的边，那么点$u$的标号要比点$v$小。求一组字典序最小的标号方案。

数据范围：$2 \le n \le 10^5, \; 1 \le m \le 10^5$。

算法分析

这是一张拓扑图，只需进行一次拓扑排序即可得到一组方案。但由于题目要求字典序最小，因此需要逆向拓扑，并用优先队列维护 id 最大的节点。证明如下：

对于节点$1$，它的标号等于它在逆向拓扑树上的子树大小，这显然属于字典序最小的方案。对于节点$2$，它的标号等于节点$1$子树并上节点$2$子树的大小，这也属于字典序最小的方案。以此类推，每个节点的标号都属于字典序最小的方案。

由此得证。

代码

#include <iostream>
#include <queue>
using namespace std;
struct edge { int v, nxt; } e[100001];
int n, m, nume, cnt, h[200001], in[200001], id[200001];
priority_queue<int> que;
void add_edge(int u, int v) {
  e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
int main()
{
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v; cin >> u >> v;
    add_edge(v, u), ++in[u];
  }
  for (int i = 1; i <= n; ++i) if (!in[i]) que.push(i);
  while (!que.empty()) {
    int u = que.top(); que.pop(), id[u] = cnt++;
    for (int i = h[u]; i; i = e[i].nxt) {
      --in[e[i].v]; if (!in[e[i].v]) que.push(e[i].v);
    }
  }
  for (int i = 1; i <= n; ++i) cout << n - id[i] << ' ';
  cout << endl;
  return 0;
}