自己写:算出并行要几轮
还是那七个构建任务。这次机器不限:一轮里所有"依赖都做完了"的任务可以同时开工。layers 已经写好了。补全 rounds,输出串行轮数和并行轮数。
⚠️ 砍掉一条依赖,有的省时间有的白砍
还是那七个构建任务。这次机器不限:一轮里所有"依赖都做完了"的任务可以同时开工。现在允许你砍掉一条依赖。分别砍掉 1 → 3 和 3 → 4,各输出砍完之后的并行轮数。
自己写:每个任务最早能第几轮开工
还是那七个构建任务。这次机器不限:一轮里所有"依赖都做完了"的任务可以同时开工。上一道给的是"每层有几个",这道要"每个任务在第几层"。按任务编号 0~6 的顺序输出各自最早的开工
「强连通」说的是什么
有向图里说两个点强连通,意思是【0】。
⚠️ 一个分量最少能有几个点
一个点,如果没有任何一条环经过它,那它自己【0】。
有几个分量,最大的那个多大
还是那七个点,这次把 5 → 3 那条边加回来,于是图里有了环: G = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 3), (4, 6)] N = 7 def build(e
最大的那个分量里是哪几个点
还是那七个点,这次把 5 → 3 那条边加回来,于是图里有了环: G = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 3), (4, 6)] N = 7 def build(e
自己写:第二遍在反图上收点
还是那七个点,这次把 5 → 3 那条边加回来,于是图里有了环:第一遍的完成顺序 order_by_finish 已经写好了。补全第二遍——在反图 rg 上按完成顺序的逆序收点,输出分量个数和最大分量的大小。
⚠️ 第二遍忘了换反图会怎样
还是那七个点,这次把 5 → 3 那条边加回来,于是图里有了环:补上选图那一行:second_reversed 为真走反图,为假就是写错的那一版(第二遍还走原图)。两版各跑一次,输出各自的分量个数。
自己写:列出互相都走得到的点对
还是那七个点,这次把 5 → 3 那条边加回来,于是图里有了环:comp[u] 是 u 所在分量的编号。列出所有互相都走得到的点对。