题目描述
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; }