快乐的一天从AC开始 | 20210711 | CF1547G

题目链接

组长分了个需求,但是没信心能写好,看来又是自闭的一周。不过好在终于可以不是纯带薪自习了。

心路历程

昨晚看完题就猜是SCC然后乱搞,也猜对了。

好像纯DFS也能写。

思路

首先,通过一次DFS可以确定答案是0,1,2的点。就节点可以至多经过两次,这样复杂度还是线性的,且能确定一个点是否可达,可达的路是否超过1条。

然后就看那些点的答案是-1。如果一个点可达,且它在一个环上(可以是自环),那么它可以到达的点(包括自身)的答案都为-1。这样子,就可以通过SCC跑出来那些点在环上,再通过一次BFS找出它可达的点。

然后跑SCC可以tarjan,也可以kosaraju。(感觉kosaraju好写一点,不过tarjan的扩展性更强?

原文地址:https://www.cnblogs.com/zengzk/p/15000292.html