在线评测链接:P1229 (opens new window)

题目内容

塔子哥是一名软件工程师，他正在为一家游戏公司开发一个新的3D引擎。这个引擎由多个模块组成，每个模块负责不同的功能，比如渲染、物理、音效、网络等。

为了提高性能和稳定性，塔子哥需要在游戏启动时初始化这些模块，但是有一个问题：不同的模块之间存在依赖关系，比如渲染模块依赖于物理模块，音效模块依赖于网络模块等。如果塔子哥不按照正确的顺序初始化这些模块，就会导致错误或崩溃。

为了解决以上问题，塔子哥决定开发一个代码分析工具，用来分析代码模块之间的依赖关系，用来确定模块的初始化顺序、是否有循环依赖等问题。

塔子哥的工具可以一次初始化一个或多个模块，只要它们之间没有依赖关系。他把这个过程称为引擎模块初始化。

现在，塔子哥已经得到了一组模块间的依赖关系，塔子哥需要计算需要引擎模块初始化的次数。

输入描述

输入第一行为一个整数 $n$ ，表示模块总数。

接下来的 $n$ 行依次表示模块 $1$ 到 $n$ 的依赖关系。

输入每行的第一个数为一个整数 $m$ ，表示依赖的模块数量(不会超过 $n$ )，之后的数字表示当前模块依赖的模块ID序列，该序列不会重复出现相同的数字，并且模块ID的取值一定在 $[1,n]$ 之内。

每一行里面的数字按一个空格分隔。

$1\le m\le n \le 1000$

输出描述

输出”批量初始化次数”。

若有循环依赖无法完成初始化，则输出 $-1$ 。

样例

样例一

输入

5
3 2 3 4
1 5
1 5
1 5
0

输出

3

样例解释

共 $5$ 个模块。

模块 $1$ 依赖模块 $2$ 、 $3$ 、 $4$ ；

模块 $2$ 依赖模块 $5$ ；

模块 $3$ 依款模块 $5$ ；

模块 $4$ 依赖模块 $5$ ；

模块 $5$ 没有依赖任何模块。

批量初始化顺序为 $\{5\}\rightarrow \{2,3,4\}\rightarrow \{1\}$ ，共需”批量初始化” $3$ 次。

样例二

输入

3
1 2
1 3
1 1

输出

-1

样例解释

存在循环依赖，无法完成初始化，返回 $-1$ 。

思路

思路讲解以及ac代码+注释(C++/Python/Java)请进入咱们的华为校招机考题库 (opens new window)查看。同时里面包含100+道真题，华为校招经验分享 (opens new window)以及刷题备考通关题单 (opens new window)，欢迎大家进入查看。