⚠️ 两条路算分量数,必须对得上

还是那七个点,这次把 5 → 3 那条边加回来,于是图里有了环:上面用的是 Kosaraju。再用笨办法数一遍:每一对点正反各跑一次可达性,互相到得了的归成一组。两个数输出出来对账。

开始练习 →

缩完之后得到的一定是什么

把每个强连通分量捏成一个点之后,剩下的图一定是【0】。

开始练习 →

⚠️ 缩点是为了解决什么麻烦

一张有环的有向图上,拓扑排序排不全、DAG 上的递推也没法填。缩点解决的正是【0】。

开始练习 →

缩完还剩几个点几条边

把上一节那张有环的图缩点:每个强连通分量捏成一个点,分量之间的边保留(去掉重边和自环)。原图是七个点八条边。 G = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 3), (4,

开始练习 →

⚠️ 缩完之后合法顺序反而变少了

把上一节那张有环的图缩点:每个强连通分量捏成一个点,分量之间的边保留(去掉重边和自环)。n01 里那张 DAG 有 4 种合法顺序。缩点之后的这张图有几种?两个数一起输出: G = [(0, 1), (0, 2), (1, 3), (2,

开始练习 →

自己写:把缩点后的图建出来

把上一节那张有环的图缩点:每个强连通分量捏成一个点,分量之间的边保留(去掉重边和自环)。comp[u] 已经算好了。建出缩点后的边集 ce,输出去重后的边数和 ce 的长度——两个数应该一样。

开始练习 →

自己写:缩点后最长的一条链

把上一节那张有环的图缩点:每个强连通分量捏成一个点,分量之间的边保留(去掉重边和自环)。缩完是一张 DAG,可以放心求最长链了。补全 longest,输出最长的一条链经过几个分量。

开始练习 →

自己写:从哪几个点出发能走遍全图

把上一节那张有环的图缩点:每个强连通分量捏成一个点,分量之间的边保留(去掉重边和自环)。缩点后如果入度为 0 的分量只有一个,那个分量里的点就能走到全图;有两个或更多就谁也走不遍。输出那几个点,没有就输出没有。

开始练习 →

⚠️ 缩点前排不全,缩点后排得全

把上一节那张有环的图缩点:每个强连通分量捏成一个点,分量之间的边保留(去掉重边和自环)。拿同一个 kahn_len,在原图和缩点后的图上各排一次,输出各自排出来的个数。

开始练习 →

⚠️ 最大流卡在哪儿

一张管道网,从水源到出口每秒最多能过多少水,取决于【0】。

开始练习 →