应该wa了第十个点的人看了题解或讨论都知道,判断条件要写dfn[v]<=dfn[b]而不是dfn[u]<dfn[b],
那这是为什么呢?我们可以来看一下这一组数据:
7
5 1
1 2
2 6
2 3
3 4
4 5
6 7
0 0
1 3
建出来的图是这样的:

然而我们会发现,写前者跑出来的正解是 No solution,而后者却跑出来了 2。这是因为在从 2 搜 6 这课子树时,dfnu 已经处理出来是 2,而 dfnb 是 3,会错误地判断出“2 阻断了 1 和 3 之间的道路”这一结论,而严格地搜索子树 v 则不会出错。
见到很多题解没有解释该写法错误的原因,故发此帖,顺便提供一组小 hack 数据。
ps:若用邻接表,可以将数据中的 5 1和2 6放到后面,主要是为了先搜到 3 再搜到 6。