# 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.

## 代码

#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;
}
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;
}

418 I'm a teapot