自动搬运

查看原文

来自洛谷，原作者为

	览遍千秋 将伤与泪汇成力化作拳

搬运于2025-08-24 21:15:32，当前版本为作者最后更新于2023-09-24 22:49:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2023 年 09 月语言月赛，由洛谷网校入门计划/基础计划提供。

考察递归。

文字题解

安装软件包 $i$ 之前，需要安装该软件包的所有依赖。安装依赖之前，又需要安装依赖的依赖，很容易，这构成了一个递归的问题。

由于一个软件包只能被安装一次，我们可以用数组 installed[i] 来表示第 $i$ 个软件包有没有被安装过。

定义函数 void f(int x)，用来表示当前正在处理编号为 $x$ 的软件包。如果 installed[x] 为 true，则说明编号为 $x$ 的软件包已经被安装了，我们无需处理，直接退出该函数即可。

如果 installed[x] 为 false，则开始处理 $x$ 的软件包依赖。遍历 $x$ 所有依赖的包 $v$，调用函数 f(v) 来处理其安装。处理完所有依赖后，将 installed[x] 修改为 true。

最后，installed 数组中为 true 的位置的个数即为答案。

以下为伪代码：

void f(int x)
    if installed[x] is true:
        return
    else:
        for v is relied by x
            f(v)
        installed[x] := true

这样一个算法的时间复杂度是 $O(n)$，可以通过。

拓展内容

当然，我们可以用有向边来描述这样一个依赖关系，如果在安装软件包 $x$ 之前，必须要安装软件包 $v$，我们就用有向边 $v \rightarrow x$ 来描述这样一个关系。

由于不存在循环依赖，在这样一个依赖关系构成的有向图中，不存在环。这是一张有向无环图（Directed Acyclic Graph，DAG），可以使用拓扑排序得到它的一个拓扑序，再用递推求解答案。

这样一个算法的时间复杂度也是 $O(n)$。

视频题解