题目
分析
这道题初看还是一道入门题目，对图进行遍历即可。但有两个问题。
- 如果从起点开始遍历它能到达的终点，那么复杂度会大大提高：对于
N个节点，M条边而言，每个节点需要遍历N+M次，因此总的复杂度是O(N(N+M))，太大了。 - 由于图可能比较复杂——如出现闭环——那么会造成DFS时，某个节点等待下一个、下一个等待节点自己返回的问题。
我们看一个示例：
flowchart TD
1-->2
2-->4
4-->3
3-->2
在这个图中，2/3/4三个节点构成了闭环。在询问1能达到的最大节点时，会陷入2-4-3-2-...的循环。而2显然不是1能达到的最大节点。
解决方法，是反过来想：不是让节点去找它能找到的最大节点，而是让每个节点表明自己能由哪里来到。
还以样本输入为例：
1 2
2 4
4 3
flowchart TD
1-->2
2-->4
4-->3
显然，结果应该是4 4 3 4。
算法分步
-
反向建图：
- 边1→2变为2←1
- 边2→4变为4←2
- 边4→3变为3←4
- 最终反向图：
graph[2] = {1}, graph[4] = {2}, graph[3] = {4}
-
反向遍历：
- 对于
i=4：ans[4]=0，执行dfs(4,4)- 更新
ans[4]=4：节点自己总是可以从自己“出发”来到自己 - 遍历
graph[4]={2}，递归dfs(2,4) - 更新
ans[2]=4：节点4还可以从2而来 - 遍历
graph[2]={1}，递归dfs(1,4) - 更新
ans[1]=4，因为2能从1而来，所以4也能从1而来
- 对于
i=3：ans[3]=0，执行dfs(3,3)- 更新
ans[3]=3 - 遍历
graph[3]={4}，但ans[4]=4>3，跳过：3虽然也能从4而来，但是ans[4]表明它可以到一个更大的节点。
- ... ...
- 对于
这样的算法，每个节点遍历一次，每次遍历所有的边即可，复杂度降低到了O(N+M)。
答案
思考
为什么反向建图可以解决闭环问题？这是因为：
- 正向遍历时，一个节点可能有多个"终点"。
- 反向遍历时，一个节点只需要记录能到达的最大节点。
- 这样就避免了在闭环中死循环的问题。