题目描述

塔子哥是一名资深软件工程师,他正在开发一个代码依赖分析工具。这个工具需要分析软件模块之间的依赖关系,用来优化代码的编译和构建过程。

题面描述:

题目要求计算给定模块间的依赖关系所需的最少“批量构建”次数，输入由一个正整数 $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$ 的有向边。