P3387【缩点】

P3387 【模板】缩点

好问。 你可以看tarjan算法里low数组的定义是什么,以及tarjan算法的正确性证明。 不过,可以证明,在使用tarjan算法缩点的过程中,两种写法是等价的。
by mashduihca @ 2023-03-08 12:27:14


@[mashduihca](/user/494183) low是回溯点
by Ly_boy @ 2023-03-22 13:31:44


有向图里两种是等价的,但无向图就不是了(无向图用的是前者,具体的可以看一下P8435题解区中大佬们的解释 ~~(我自己懂,但是解释不明白)~~)
by Bodhi @ 2023-04-03 23:21:03


|