Minimal Labels
题目描述
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$子树的大小,这也属于字典序最小的方案。以此类推,每个节点的标号都属于字典序最小的方案。
由此得证。
代码
1 |
|
Minimal Labels
https://regmsif.cf/2017/07/17/oi/minimal-labels/