请求撤下题解
查看原帖
请求撤下题解
589916
August_Light楼主2023/5/13 16:36

请求撤下我同学 fy12333 的题解 P3388 Solution。

存在事实性错误:

tarjan 的用处很多,能解决强连通分量,双连通分量,割点与桥,还能求 LCA。

求解连通性问题的 Tarjan 算法和求解 LCA 的 Tarjan 算法有着根本上的区别。

我们需要开两个新数组 dfn 和 low。这两个数组分别表示 DFS 访问到的顺序(也叫时间戳)以及不经过其父亲能到达的最小的时间戳。

"不经过其父亲能到达的最小的时间戳"是错误的。

对于一张这样的图,假设程序以 1→2→3→4→51 \to 2 \to 3 \to 4 \to 5 这样的顺序 dfs 它,那么 55 不经过父亲节点 44 所能到达的最小 dfndfn 应该是 11 而非实际上 low5low_5 的值 33。

其它还有一些小地方,比如有时使用 dfnudfn_u 有时使用 dfn[u]dfn[u],Tarjan 的 T 应大写,代码中链式前【项】星错别字。

以及我认为讲解不够清晰,没有讲清楚 Tarjan 算法中开栈的作用。

2023/5/13 16:36
加载中...