E. Minimal Labels

Codeforces

IDCF825E

Time1000ms

Memory256MB

Difficulty—

data structuresdfs and similargraphsgreedy

English · Original

Chinese · Translation

Formal · Original

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. ## Input The first line contains two integer numbers _n_, _m_ (2 ≤ _n_ ≤ 105, 1 ≤ _m_ ≤ 105). Next _m_ lines contain two integer numbers _v_ and _u_ (1 ≤ _v_, _u_ ≤ _n_, _v_ ≠ _u_) — edges of the graph. Edges are directed, graph doesn't contain loops or multiple edges. ## Output Print _n_ numbers — lexicographically smallest correct permutation of labels of vertices. [samples]

给定一个有 #cf_span[n] 个顶点和 #cf_span[m] 条边的有向无环图。图中不存在自环，任意两个顶点之间也不存在多条边。图可以是不连通的。你需要为所有顶点分配标签，使得：找到满足所有条件的标签序列。第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2 ≤ n ≤ 105, 1 ≤ m ≤ 105])。接下来 #cf_span[m] 行每行包含两个整数 #cf_span[v] 和 #cf_span[u] (#cf_span[1 ≤ v, u ≤ n, v ≠ u]) —— 图的边。边是有向的，图中不包含环或多重边。请输出 #cf_span[n] 个数字 —— 顶点标签的字典序最小的合法排列。 ## Input 第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2 ≤ n ≤ 105, 1 ≤ m ≤ 105])。接下来 #cf_span[m] 行每行包含两个整数 #cf_span[v] 和 #cf_span[u] (#cf_span[1 ≤ v, u ≤ n, v ≠ u]) —— 图的边。边是有向的，图中不包含环或多重边。 ## Output 请输出 #cf_span[n] 个数字 —— 顶点标签的字典序最小的合法排列。 [samples]

**Definitions** Let $ G = (V, E) $ be a directed acyclic graph (DAG), where: - $ V = \{1, 2, \dots, n\} $ is the set of vertices, - $ E \subseteq V \times V $ is the set of directed edges, with $ |E| = m $, - No self-loops or multiple edges: $ (v, u) \in E \Rightarrow v \ne u $, and no duplicate edges. Let $ \ell: V \to \{1, 2, \dots, n\} $ be a bijection (labeling) assigning distinct integer labels from $ 1 $ to $ n $ to the vertices. **Constraints** For every directed edge $ (v, u) \in E $, it must hold that: $$ \ell(v) < \ell(u) $$ **Objective** Find the lexicographically smallest such labeling $ \ell $ satisfying all edge constraints.

Samples

Input #1

Output #1

1 3 2

Input #2

Output #2

4 1 2 3

Input #3

Output #3

3 1 2 4 5

API Response (JSON)

{
  "problem": {
    "name": "E. Minimal Labels",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF825E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\n\nYou should assign labels to ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个有 #cf_span[n] 个顶点和 #cf_span[m] 条边的有向无环图。图中不存在自环，任意两个顶点之间也不存在多条边。图可以是不连通的。\n\n你需要为所有顶点分配标签，使得：\n\n找到满足所有条件的标签序列。\n\n第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2 ≤ n ≤ 105, 1 ≤ m ≤ 105])。\n\n接下来 #cf_span[...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a directed acyclic graph (DAG), where:  \n- $ V = \\{1, 2, \\dots, n\\} $ is the set of vertices,  \n- $ E \\subseteq V \\times V $ is the set of directed edges, with ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments