2309H pip install

览遍千秋 · 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)。