AlgoMooc
← 返回题库

P3752. 快速开租建站

中等通过率 72% · 提交 369 · 通过 266
BFS图论拓扑排序模拟

小慕正在负责公司内部一个全新的自动化开站项目。所谓开站,就是在完全空白的环境里,部署一套完整的 IT 服务。每个站点的开站过程由一系列部署任务组成,每个任务的部署时间固定且相等,记为 1。任务之间可能存在关系:如果任务 B 依赖任务 A,那么必须等任务 A 部署完成后,任务 B 才能开始部署。如果某个任务有多个依赖任务,则需要等待所有依赖任务都完成后,该任务才能启动。没有依赖关系的任务可以同时,小慕和团队能做到完全并行、毫无等待。现在,给定一个站点的所有部署任务及其依赖关系,请你帮小慕计算出这个站点最短需要多长时间才能完成开站。

提示:带虚线的词点一下有通俗解释。

输入描述

第一行是任务数 taskNum,第二行是任务的依赖关系数 relationsNum 接下来 relationsNum 行,每行包含两个 id,描述一个依赖关系,格式为:IDi IDj,表示部署任务 i 部署完成了,部署任务 j 才能部署,IDi 和 IDj 值的范围为:[0, taskNum) 注:输入保证部署任务之间的依赖不会存在环。

输出描述

一个整数,表示一个站点的最短开站时间。

示例

示例 1

输入

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

输出

3

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。