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

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

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

阅读更多 →
自己写:从哪几个点出发能走遍全图

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

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

阅读更多 →
自己写:缩点后最长的一条链

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

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

阅读更多 →
自己写:把缩点后的图建出来

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

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

阅读更多 →
⚠️ 缩完之后合法顺序反而变少了

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

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

阅读更多 →
缩完还剩几个点几条边

缩完还剩几个点几条边

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

阅读更多 →
⚠️ 缩点是为了解决什么麻烦

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

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

阅读更多 →
缩完之后得到的一定是什么

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

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

阅读更多 →
⚠️ 两条路算分量数,必须对得上

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

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

阅读更多 →
自己写:列出互相都走得到的点对

自己写:列出互相都走得到的点对

还是那七个点,这次把 5 → 3 那条边加回来,于是图里有了环:comp[u] 是 u 所在分量的编号。列出所有互相都走得到的点对。

阅读更多 →