English · Original
Chinese · Translation
Formal · Original
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 cities reachable from the capital?
New roads will also be one-way.
## Input
The 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$.
The 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$).
## Output
Print 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_.
[samples]
## Note
The first example is illustrated by the following:
<center></center>For example, you can add roads ($6, 4$), ($7, 9$), ($1, 7$) to make all the cities reachable from $s = 1$.
The second example is illustrated by the following:
<center></center>In 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$.
在 Berland 有 $n$ 座城市和 $m$ 条道路。每条道路连接一对城市。Berland 的道路是单向的。
求最少需要新建多少条道路，才能使所有城市都能从首都到达？
新建的道路也将是单向的。
输入的第一行包含三个整数 $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$）。
请输出一个整数——使所有城市都能从城市 $s$ 到达所需新增的最少道路数。如果所有城市已经可以从 $s$ 到达，请输出 _0_。
第一个示例如下图所示：
例如，你可以添加道路 ($6, 4$)、($7, 9$)、($1, 7$)，使得所有城市都能从 $s = 1$ 到达。
第二个示例如下图所示：
在这个例子中，你可以添加任意一条道路 ($5, 1$)、($5, 2$)、($5, 3$)、($5, 4$)，使得所有城市都能从 $s = 5$ 到达。
## Input
输入的第一行包含三个整数 $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$）。
## Output
输出一个整数——使所有城市都能从城市 $s$ 到达所需新增的最少道路数。如果所有城市已经可以从 $s$ 到达，请输出 _0_。
[samples]
## Note
第一个示例如下图所示：
例如，你可以添加道路 ($6, 4$)、($7, 9$)、($1, 7$)，使得所有城市都能从 $s = 1$ 到达。
第二个示例如下图所示：
在这个例子中，你可以添加任意一条道路 ($5, 1$)、($5, 2$)、($5, 3$)、($5, 4$)，使得所有城市都能从 $s = 5$ 到达。
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.
Let $ R \subseteq V $ be the set of vertices reachable from $ s $ via directed paths in $ G $.
Define the set of unreachable vertices: $ U = V \setminus R $.
Let $ 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 $).
Let $ \text{indeg}_{\text{external}}(C_i) $ denote the number of edges from $ R $ to vertices in $ C_i $.
Let $ Z \subseteq C $ be the set of SCCs in $ U $ with $ \text{indeg}_{\text{external}}(C_i) = 0 $.
Then, the minimum number of new one-way roads required to make all vertices reachable from $ s $ is:
$$
|Z|
$$
API Response (JSON)
{
"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 cit...",
"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$）——分别表...",
"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 reach...",
"is_translate": false,
"language": "Formal"
}
]
}