题面描述:
题目要求计算给定模块间的依赖关系所需的最少“批量构建”次数，输入由一个正整数 N 表示模块总数，接下来的 N 行描述每个模块的依赖关系，第一项是该模块依赖的模块数量，后续项是具体的模块编号。如果存在循环依赖导致无法完成构建，则输出 −1；如果没有，则输出所需的最少“批量构建”次数。例如，对于输入 5\n3 2 3 4\n1 5\n1 5\n1 5\n0，输出应为 3；对于输入 3\n1 2\n1 3\n1 1，输出应为 -1。
思路
可以使用拓扑排序来解决。
将每个模块看作图中的一个节点，如果模块 A 依赖模块 B，则在图中添加一条从 B 指向 A 的有向边。
P2318.第1题-批量初始化次数
题目描述
小明是一名资深软件工程师,他正在开发一个代码依赖分析工具。这个工具需要分析软件模块之间的依赖关系,用来优化代码的编译和构建过程。
在该工具中,"批量构建"是指将多个没有依赖关系的模块一次性进行编译和构建。例如,如果模块 A 依赖模块 B 和 C,模块 D 依赖模块 C,但模块 B 和 D 之间没有依赖关系,则需要先"批量构建"模块 B 和 C,再分别构建模块 A 和 D。
现在,给定一组模块间的依赖关系,请你帮助小明计算需要"批量构建"的最少次数。
输入格式
第一行只有一个正整数 N,表示模块总数。
随后的 N 行依次表示模块 1 到 N 的依赖关系。每行的第一个数据 Ki 表示模块 i 依赖的模块数量,之后跟着 Ki 个整数,表示模块 i 依赖的模块编号。模块编号的取值范围为 [1,N],且每行中的模块编号各不相同。
输出格式
输出"批量构建"的最少次数。若存在循环依赖导致无法完成构建,则输出 −1。
样例输入1
5
3 2 3 4
1 5
1 5
1 5
0
样例输出1
3
样例输入2
3
1 2
1 3
1 1
样例输出2
-1
评测数据与规模
- 1≤N≤1000
- 0≤Ki<N
- 输入数据保证模块编号在 [1,N] 范围内,且不存在自依赖的情况。
