这道题很有必要告诫后人一下,帮助那些与我一样被困 4h+4h+4h+ 的同学。
令 nownownow 为当前 dfsdfsdfs 到的节点,yyy 为其搜索树上的一个儿子。注意,nownownow 与 yyy 在栈中不一定相邻。也就是说,下面两种写法:
① 弹出栈顶直到弹出 nownownow 为止;最后再压入 nownownow
② 弹出栈顶直到弹出 yyy 为止,最后再将虚点向 nownownow 连边
前者错误,后者正确。