代码功能概述
这段 C++ 代码主要实现了一个拓扑排序的应用,用于解决某种课程或事件之间的先后顺序问题,最终计算出完成所有任务所需的最大“层数”(这里的层数可以理解为完成任务的最大先后顺序层级)。
代码详细分析
变量定义
* n 和 m:分别表示总任务数和输入的规则数。
* a[1005]:用于临时存储每组规则中的任务编号。
* s[1005]:邻接表,用于存储图的边信息,s[i] 存储从任务 i 出发能到达的所有任务。
* mp:一个 map 容器,用于快速判断某个任务是否在当前规则中。
* vis[1005][1005]:二维数组,用于标记任务之间的边是否已经存在,避免重复添加。
* in[1005]:数组,用于记录每个任务的入度(即有多少条边指向该任务)。
* dis[1005]:数组,用于记录从入度为 0 的任务出发,到达每个任务所需的最大层数。
输入处理
* 首先读取总任务数 n 和规则数 m。
* 对于每个规则,先清空 map,然后读取该规则中的任务数量 l 和具体任务编号,将这些任务编号存入 a 数组并在 map 中标记。
* 接着遍历从 a[1] 到 a[l] 的所有任务编号,如果某个任务编号不在当前规则中(即 mp.find(j)==mp.end()),则将该任务与当前规则中的所有任务建立有向边,同时更新 vis 数组、邻接表 s 和入度数组 in。
拓扑排序
* 初始化一个队列 q,将所有入度为 0 的任务加入队列,并将它们的 dis 值初始化为 1。
* 不断从队列中取出任务,更新最大层数 maxx,并将该任务的所有后继任务的入度减 1。如果某个后继任务的入度变为 0,则将其加入队列,并更新其 dis 值为当前任务的 dis 值加 1。
输出结果
输出完成所有任务所需的最大层数。
复杂度分析
* 时间复杂度:O(m×k+n+e)O(m \times k + n + e)O(m×k+n+e),其中 mmm 是规则数,kkk 是每个规则中的任务数,nnn 是任务总数,eee 是图中的边数。
* 空间复杂度:O(n2)O(n^2)O(n2),主要用于存储 vis 数组。
注意事项
* 代码假设输入的任务编号范围在 1 到 n 之间。
* 由于使用了 #include<bits/stdc++.h>,该头文件包含了所有标准库的头文件,可能会增加编译时间,在实际项目中建议只包含所需的头文件。
完整代码: