K. Topological Sort

Codeforces

IDCF10110K

Time8000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Consider a directed graph G of N nodes and all edges (u→v) such that u < v. It is clear that this graph doesn’t contain any cycles. Your task is to find the lexicographically largest topological sort of the graph after removing a given list of edges. A topological sort of a directed graph is a sequence that contains all nodes from 1 to N in some order such that each node appears in the sequence before all nodes reachable from it. The first line of input contains a single integer T, the number of test cases. The first line of each test case contains two integers N and M (1 ≤ N ≤ 105) , the number of nodes and the number of edges to be removed, respectively. Each of the next M lines contains two integers a and b (1 ≤ a < b ≤ N), and represents an edge that should be removed from the graph. No edge will appear in the list more than once. For each test case, print N space-separated integers that represent the lexicographically largest topological sort of the graph after removing the given list of edges. ## Input The first line of input contains a single integer T, the number of test cases.The first line of each test case contains two integers N and M (1 ≤ N ≤ 105) , the number of nodes and the number of edges to be removed, respectively.Each of the next M lines contains two integers a and b (1 ≤ a < b ≤ N), and represents an edge that should be removed from the graph.No edge will appear in the list more than once. ## Output For each test case, print N space-separated integers that represent the lexicographically largest topological sort of the graph after removing the given list of edges. [samples]

**Definitions** Let $ N, M \in \mathbb{Z}^+ $. Let $ G = (V, E) $ be a directed graph with $ V = \{1, 2, \dots, N\} $ and initial edge set $ E_0 = \{(u, v) \mid 1 \le u < v \le N\} $. Let $ R \subseteq E_0 $ be the set of $ M $ removed edges, where each $ (a, b) \in R $ satisfies $ 1 \le a < b \le N $. Define the residual graph $ G' = (V, E') $ with $ E' = E_0 \setminus R $. **Constraints** 1. $ 1 \le T \le \text{number of test cases} $ 2. For each test case: - $ 1 \le N \le 10^5 $ - $ 0 \le M \le \binom{N}{2} $ - All edges in $ R $ are distinct and satisfy $ a < b $ **Objective** Find the lexicographically largest topological ordering of $ G' $. That is, find a permutation $ \pi = (\pi_1, \pi_2, \dots, \pi_N) $ of $ \{1, 2, \dots, N\} $ such that: - For every $ (u, v) \in E' $, $ \pi^{-1}(u) < \pi^{-1}(v) $, - $ \pi $ is lexicographically maximal among all valid topological orderings.

API Response (JSON)

{
  "problem": {
    "name": "K. Topological Sort",
    "description": {
      "content": "Consider a directed graph G of N nodes and all edges (u→v) such that u < v. It is clear that this graph doesn’t contain any cycles. Your task is to find the lexicographically largest topological sort",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10110K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider a directed graph G of N nodes and all edges (u→v) such that u < v. It is clear that this graph doesn’t contain any cycles.\n\nYour task is to find the lexicographically largest topological sort...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $.  \nLet $ G = (V, E) $ be a directed graph with $ V = \\{1, 2, \\dots, N\\} $ and initial edge set $ E_0 = \\{(u, v) \\mid 1 \\le u < v \\le N\\} $.  \nLet $ R \\s...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments