1 solutions
-
0
题目大意
塔子哥决定开发一个工具来分析模块之间的依赖关系,计算引擎模块初始化的次数。如果模块之间存在循环依赖,则无法完成初始化,工具应该输出 -1,表示初始化失败。
解题思路
这个问题可以抽象为拓扑排序的问题。如果模块之间没有循环依赖,我们可以通过拓扑排序确定模块初始化的顺序。如果存在循环依赖,意味着无法完成拓扑排序。
思路步骤
1.构建依赖图:
每个模块可以依赖其他模块,这可以通过有向图来表示,其中每个模块是一个节点,依赖关系是有向边。 图的边从依赖的模块指向当前模块。例如,如果模块 A 依赖于模块 B,那么边应该从 B 指向 A。
2.计算入度:
入度表示每个节点(模块)有多少个依赖关系。我们需要计算每个模块的入度,即有多少个模块是当前模块的前置依赖。
3.拓扑排序:
使用拓扑排序算法(Kahn 算法),从入度为 0 的模块开始,每次移除一个模块,并减少它所依赖模块的入度。当某个模块的入度变为 0 时,意味着它的所有前置依赖都已经被初始化,可以安全初始化这个模块。 记录执行的轮次,轮次代表每一批可以同时初始化的模块数。
4.检测循环依赖:
如果经过拓扑排序后,仍然存在某些模块没有被处理,说明存在循环依赖,输出 -1。
代码说明
1。初始化图和入度数组: 根据输入,构建每个模块的依赖关系,记录每个模块的入度。
2.处理入度为 0 的模块: 使用队列(或栈)存储所有入度为 0 的模块,开始拓扑排序。
3.拓扑排序:
每次从队列中取出一个入度为 0 的模块,处理它所依赖的模块(将其入度减 1)。 如果某个模块的入度减为 0,将其加入队列。 记录批次,每次从队列中取出模块时,都代表可以初始化这些模块。
4.检测是否存在循环依赖:
如果所有模块都被处理,输出批量初始化的轮次。 如果有模块未被处理,输出 -1,表示存在循环依赖。
C++
解法1
python
解法2
Java
Go
Js
- 1
Information
- ID
- 13
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 108
- Accepted
- 55
- Uploaded By