会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
先核对版本，再按依赖关系做拓扑排序。m 最大只有 100，直接模拟即可。
- 把每个软件包的 a.b.c 拆成三个整数，用元组比较，不要当字符串比。
- 解析依赖时先匹配
>=、<=，再匹配 >、<，否则 >= 会被拆成 >。
- 扫一遍全部依赖：实际版本不满足约束就输出
-1。
- 建图时边从被依赖者指向依赖者，表示必须先装被依赖者。自己依赖自己会形成入度为
1 且出边指向自己的环。
- 用小根堆做 Kahn 算法，每次取当前入度为
0 的最小编号，得到数字序最小的安装顺序。装不完就输出 -2。
题目内容
你正在实现一个软件包依赖分析工具。每个软件包拥有唯一编号，版本号写成三段形式 a.b.c。系统描述中每一行先给出软件包编号和版本号，之后可以跟随零个或多个依赖项；依赖项之间用空格分隔，同一行内不会重复列出同一个被依赖的软件包。
依赖项只允许采用以下 5 种写法：
编号>=版本号：表示要求该软件包的版本不低于给定版本。编号<=版本号：表示要求该软件包的版本不高于给定版本。编号>版本号：表示要求该软件包的版本严格高于给定版本。编号<版本号：表示要求该软件包的版本严格低于给定版本。编号：表示依赖该软件包，但不限制其版本。
分析工具首先需要验证所有依赖项中的版本要求是否都被实际版本满足。随后需要根据依赖关系计算安装顺序：一个软件包只有在它依赖的软件包全部安装之后才能安装。
如果版本约束无法满足，输出 -1。如果依赖关系构成环（包括软件包直接或间接依赖自身），输出 -2。如果存在可行安装顺序，则输出一个编号序列；当存在多个可行序列时，从左到右比较编号，输出字典序最小的序列。
约束条件
- 软件包数量 m 满足 1≤m≤100。
- 软件包编号为从
0 到 m−1 的整数，且各行的软件包编号互不相同。
- 版本号三段 a、b、c 均为 [0,999] 内的整数。
输入描述
第一行包含一个整数 m，表示软件包数量。
接下来的 m 行，每行描述一个软件包，依次为软件包编号、版本号、零个或多个依赖项。所有字段之间以及同一行中的多个依赖项之间都用空格分隔。
输出描述
如果版本约束有冲突，输出 -1。
如果依赖关系存在环（包括自己依赖自己），输出 -2。
否则输出一行，包含一个可行的安装顺序，软件包编号之间用一个空格分隔；如果有多个可行顺序，输出字典序最小的编号序列。
样例1
输入
1
0 0.0.0
输出
0
说明
只有一个软件包 0，版本为 0.0.0，它没有声明任何依赖项。
因此可以直接安装，唯一的安装序列就是 0。
样例2
输入
3
0 1.0.0 1<2.0.0
1 2.0.1
2 3.0.0 0>=1.0.0
输出
-1
说明
软件包 0 声明依赖 1<2.0.0，即要求软件包 1 的版本严格低于 2.0.0。
软件包 1 的实际版本是 2.0.1，不满足这一版本要求，因此版本约束冲突，输出 -1。
样例3
输入
2
0 1.0.0 1
1 2.0.0 0
输出
-2
说明
软件包 0 的依赖项是 1，表示安装 0 前必须先安装 1。
软件包 1 的依赖项是 0，表示安装 1 前又必须先安装 0。
这两个软件包互相等待，形成依赖环，因此输出 -2。
样例4
输入
3
0 1.0.0
1 2.0.0
2 3.0.0 0>=1.0.0
输出
0 1 2
说明
初始时软件包 0 和 1 都没有依赖项，当前编号最小的可安装软件包是 0，所以先安装 0。
软件包 2 的依赖项是 0>=1.0.0，而软件包 0 的实际版本 1.0.0 满足该要求。
安装 0 后，软件包 2 的依赖被满足，此时可安装的是 1 和 2，编号较小的 1 先安装，最后安装 2。
虽然 1 0 2 也是可行顺序，但 0 1 2 字典序更小，因此输出 0 1 2。
