{"problem":{"name":"E. Reachability from the Capital","description":{"content":"There are $n$ cities and $m$ roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way. What is the minimum number of new roads that need to be built to make all the cit","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF999E"},"statements":[{"statement_type":"Markdown","content":"There are $n$ cities and $m$ roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way.\n\nWhat is the minimum number of new roads that need to be built to make all the cities reachable from the capital?\n\nNew roads will also be one-way.\n\n## Input\n\nThe first line of input consists of three integers $n$, $m$ and $s$ ($1 \\le n \\le 5000, 0 \\le m \\le 5000, 1 \\le s \\le n$) — the number of cities, the number of roads and the index of the capital. Cities are indexed from $1$ to $n$.\n\nThe following $m$ lines contain roads: road $i$ is given as a pair of cities $u_i$, $v_i$ ($1 \\le u_i, v_i \\le n$, $u_i \\ne v_i$). For each pair of cities $(u, v)$, there can be at most one road from $u$ to $v$. Roads in opposite directions between a pair of cities are allowed (i.e. from $u$ to $v$ and from $v$ to $u$).\n\n## Output\n\nPrint one integer — the minimum number of extra roads needed to make all the cities reachable from city $s$. If all the cities are already reachable from $s$, print _0_.\n\n[samples]\n\n## Note\n\nThe first example is illustrated by the following:\n\nFor example, you can add roads ($6, 4$), ($7, 9$), ($1, 7$) to make all the cities reachable from $s = 1$.\n\nThe second example is illustrated by the following:\n\nIn this example, you can add any one of the roads ($5, 1$), ($5, 2$), ($5, 3$), ($5, 4$) to make all the cities reachable from $s = 5$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在 Berland 有 $n$ 座城市和 $m$ 条道路。每条道路连接一对城市。Berland 的道路是单向的。\n\n求最少需要新建多少条道路，才能使所有城市都能从首都到达？\n\n新建的道路也将是单向的。\n\n输入的第一行包含三个整数 $n$、$m$ 和 $s$（$1 lt.eq n lt.eq 5000$，$0 lt.eq m lt.eq 5000$，$1 lt.eq s lt.eq n$）——分别表示城市数量、道路数量和首都的编号。城市编号从 $1$ 到 $n$。\n\n接下来的 $m$ 行描述道路：第 $i$ 条道路由一对城市 $u_i$、$v_i$ 给出（$1 lt.eq u_i, v_i lt.eq n$，$u_i != v_i$）。对于每对城市 $(u, v)$，最多存在一条从 $u$ 到 $v$ 的道路。允许在一对城市之间存在相反方向的道路（即从 $u$ 到 $v$ 和从 $v$ 到 $u$）。\n\n请输出一个整数——使所有城市都能从城市 $s$ 到达所需新增的最少道路数。如果所有城市已经可以从 $s$ 到达，请输出 _0_。\n\n第一个示例如下图所示：\n\n例如，你可以添加道路 ($6, 4$)、($7, 9$)、($1, 7$)，使得所有城市都能从 $s = 1$ 到达。\n\n第二个示例如下图所示：\n\n在这个例子中，你可以添加任意一条道路 ($5, 1$)、($5, 2$)、($5, 3$)、($5, 4$)，使得所有城市都能从 $s = 5$ 到达。\n\n## Input\n\n输入的第一行包含三个整数 $n$、$m$ 和 $s$（$1 lt.eq n lt.eq 5000$，$0 lt.eq m lt.eq 5000$，$1 lt.eq s lt.eq n$）——分别表示城市数量、道路数量和首都的编号。城市编号从 $1$ 到 $n$。接下来的 $m$ 行描述道路：第 $i$ 条道路由一对城市 $u_i$、$v_i$ 给出（$1 lt.eq u_i, v_i lt.eq n$，$u_i != v_i$）。对于每对城市 $(u, v)$，最多存在一条从 $u$ 到 $v$ 的道路。允许在一对城市之间存在相反方向的道路（即从 $u$ 到 $v$ 和从 $v$ 到 $u$）。\n\n## Output\n\n输出一个整数——使所有城市都能从城市 $s$ 到达所需新增的最少道路数。如果所有城市已经可以从 $s$ 到达，请输出 _0_。\n\n[samples]\n\n## Note\n\n第一个示例如下图所示：\n例如，你可以添加道路 ($6, 4$)、($7, 9$)、($1, 7$)，使得所有城市都能从 $s = 1$ 到达。\n\n第二个示例如下图所示：\n在这个例子中，你可以添加任意一条道路 ($5, 1$)、($5, 2$)、($5, 3$)、($5, 4$)，使得所有城市都能从 $s = 5$ 到达。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ G = (V, E) $ be a directed graph with $ |V| = n $ vertices (cities) and $ |E| = m $ edges (one-way roads). Let $ s \\in V $ denote the capital.\n\nLet $ R \\subseteq V $ be the set of vertices reachable from $ s $ via directed paths in $ G $.\n\nDefine the set of unreachable vertices: $ U = V \\setminus R $.\n\nLet $ C = \\{ C_1, C_2, \\dots, C_k \\} $ be the set of strongly connected components (SCCs) of the subgraph induced by $ U $, ordered in topological order (i.e., if there is a path from a vertex in $ C_i $ to a vertex in $ C_j $, then $ i < j $).\n\nLet $ \\text{indeg}_{\\text{external}}(C_i) $ denote the number of edges from $ R $ to vertices in $ C_i $.\n\nLet $ Z \\subseteq C $ be the set of SCCs in $ U $ with $ \\text{indeg}_{\\text{external}}(C_i) = 0 $.\n\nThen, the minimum number of new one-way roads required to make all vertices reachable from $ s $ is:\n\n$$\n|Z|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF999E","tags":["dfs and similar","graphs","greedy"],"sample_group":[["9 9 1\n1 2\n1 3\n2 3\n1 5\n5 6\n6 1\n1 8\n9 8\n7 1","3"],["5 4 5\n1 2\n2 3\n3 4\n4 1","1"]],"created_at":"2026-03-03 11:00:39"}}