CSES 1699 Flight Route Requests 题解

一、问题转化

对于每个请求 $a \to b$，我们只需要保证最终存在一条从城市 $a$ 到城市 $b$ 的路径。

需要注意：

• 请求 $a \to b$ 不代表必须直接建立一条航班 $a \to b$；
• 可以经过其他城市；
• 允许额外产生题目没有要求的可达关系。

例如，请求为：

1 -> 2
2 -> 3
1 -> 3

只需要建立：

1 -> 2
2 -> 3

因为城市 $1$ 可以经过城市 $2$ 到达城市 $3$。

因此，我们先把所有请求看成一张有向图，称为“请求图”。

---

二、划分弱连通分量

暂时忽略请求边的方向，把每条有向边 $a \to b$ 看成一条无向边 $a-b$。

这样可以将整张图划分成若干个弱连通分量。

例如：

1 -> 2
3 -> 4

忽略方向后得到两个弱连通分量：

{1,2}
{3,4}

不同弱连通分量之间没有任何请求关系，因此可以分别计算答案，最后求和。

没有出现在任何有效请求中的城市，可以看成大小为 $1$ 的弱连通分量，对答案的贡献为 $0$。

设当前弱连通分量中有 $k$ 个城市，下面分两种情况讨论。

---

三、情况一：分量内部没有有向环

如果该弱连通分量中不存在有向环，那么它是一张 DAG，即有向无环图。

我们可以对这 $k$ 个城市进行拓扑排序，得到：

$$v_1,v_2,\ldots,v_k$$

然后建立下面这条链：

$$v_1\to v_2\to\cdots\to v_k$$

一共需要建立 $k-1$ 条航班。

为什么这样能够满足所有请求？

如果请求图中存在一条边 $u\to v$，根据拓扑序的性质，$u$ 一定排在 $v$ 前面。

建立上述链以后，排在前面的城市都能到达排在后面的城市，因此一定存在从 $u$ 到 $v$ 的路径。

所以原来的所有请求都会得到满足。

为什么不能少于 $k-1$ 条？

忽略边的方向后，这 $k$ 个城市属于同一个连通分量。

要让 $k$ 个不同城市连在一起，至少需要 $k-1$ 条边。

因此，当弱连通分量中不存在有向环时，最少需要：

$$k-1$$

条航班。

---

四、情况二：分量内部存在有向环

如果该弱连通分量中存在有向环，那么最少需要 $k$ 条航班。

为什么 $k$ 条一定足够？

将这 $k$ 个城市按照任意顺序排列：

$$v_1,v_2,\ldots,v_k$$

然后建立一个大环：

$$v_1\to v_2\to\cdots\to v_k\to v_1$$

一共建立 $k$ 条航班。

形成大环以后，任意一个城市都能到达其他所有城市，所以原请求图中的所有请求一定能够得到满足。

为什么不能少于 $k$ 条？

由于原请求图中存在有向环，最终建立的航班图中也必须能够实现这个有向环上的所有可达关系。

同时，这个弱连通分量中的 $k$ 个城市在忽略方向后必须连在一起。

一个连通图如果包含环，那么它的边数至少等于点数。因此至少需要 $k$ 条航班。

所以，当弱连通分量中存在有向环时，最少需要：

$$k$$

条航班。

---

五、结论

对于一个包含 $k$ 个城市的弱连通分量：

• 如果内部没有有向环，答案为 $k-1$；
• 如果内部存在有向环，答案为 $k$。

可以统一写成：

$$\text{贡献}=k-1+\text{hasCycle}$$

其中：

• hasCycle = 0 表示该弱连通分量没有有向环；
• hasCycle = 1 表示该弱连通分量存在有向环。

最终答案就是所有弱连通分量贡献之和。

---

六、如何判断弱连通分量中是否存在有向环

可以同时使用并查集和 Tarjan 算法。

并查集的作用

对于每个请求 $a\to b$，忽略方向，在并查集中合并 $a$ 和 $b$。

这样就可以得到每个弱连通分量，并统计其中包含的城市数量。

Tarjan 的作用

在有向请求图上运行 Tarjan 算法，求出所有强连通分量。

如果一个强连通分量的点数大于 $1$，那么其中一定存在有向环。

因此，可以将这个强连通分量所在的弱连通分量标记为“存在有向环”。

---

七、算法流程

1. 读入每个请求 $a\to b$。
2. 在有向图中加入边 $a\to b$。
3. 在并查集中合并城市 $a$ 和城市 $b$。
4. 使用 Tarjan 算法求出所有强连通分量。
5. 如果某个强连通分量的大小大于 $1$，标记其所在的弱连通分量存在有向环。
6. 统计每个弱连通分量的城市数量。
7. 对每个并查集根节点累加：

size[root]-1+hasCycle[root]

如果出现 $a=b$ 的请求，可以直接忽略，因为城市本身已经可以到达自己，不需要建立航班。

---

八、样例分析

样例中的请求为：

1 -> 2
2 -> 3
2 -> 4
3 -> 1
3 -> 4

忽略方向后，城市 $1,2,3,4$ 属于同一个弱连通分量。

同时存在有向环：

$$1\to2\to3\to1$$

因此这个弱连通分量：

• 城市数量为 $k=4$；
• 内部存在有向环。

所以它对答案的贡献为：

$$k=4$$

最终答案为：

4

一种可行的航班建立方案为：

1 -> 2
2 -> 3
3 -> 1
2 -> 4

其中请求 $3\to4$ 可以通过下面的路径实现：

$$3\to1\to2\to4$$

---

九、复杂度分析

并查集的时间复杂度接近线性。

Tarjan 算法的时间复杂度为：

$$O(n+m)$$

因此总时间复杂度为：

$$O(n+m)$$

空间复杂度为：

$$O(n+m)$$

---

十、总结

这道题最重要的结论是：

将请求图按照弱连通分量划分。对于每个弱连通分量，如果内部没有有向环，就把所有城市按照拓扑序连成一条链，需要“点数减一”条边；如果内部存在有向环，就把所有城市连成一个大环，需要“点数”条边。

所以每个弱连通分量的答案为：

点数 - 1 + 是否存在有向环