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.


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






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

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *