明明就是usaco的水题嘛有啥好写的ovo只是想mark一下刚自己想出来的非递归的正常版的tarjan.
这题思路灰常简单.就tarjan缩scc然后在dag上找一下最长路就完了.
然后就是非递归的tarjan.考虑平时用栈建树的dfs序的方法,既把一个点的所有儿子扔进栈再递归.然而这个方法不能直接套进tarjan的dfs.因为它的一个儿子可能会对另一个儿子造成影响,有可能甚至直接改变dfs的顺序.
所以如果更新的时候一个点连出去的点还没有被访问,那么不管它是否已经在栈里,都再把它扔进去一次.这样就保证了访问的顺序.而在再次访问的时候只要判断一下是否已经访问就行了.
然后对于两个更新,首先如果直接low[p]=dfn[p]的话是不需要专门去用dfn来取min的.然后考虑倒着更新.每个点被退visit栈的时候去更新它的父亲就好.因为它的父亲一定还没有出栈.然后如果是只更新不递归那就直接访问.
这样的话空间复杂度会变成O(n+m),不过妈妈再也不用担心我暴栈了.而这个方法也比强行模拟系统栈要方便一些.
开心ovo