警示后人:关于重边

P8436 【模板】边双连通分量

hm2ns @ 2024-04-10 22:57:29

如图,像这样的带有重边的无向图也是边双:

因此,在存边时不应去掉重边;在使用 tarjan 算法时记录的不应是 从哪一个点过来,而是 到达这个点经过的边的反向边是哪条,以避免忽略了另一条无向边。
因此被卡 1h,警钟长鸣。


|