[LeetCode]Find Eventual Safe States

能不能停在某个节点就意味着从这个点开始能不能到达某个cycle，如果可以，那么我们显然是没有办法停在一个节点的，否则的话肯定可以。所以首先我们可以用dfs来解这道题，dfs可以帮助我们detect cycle，如果我们检测到了一个在环上的节点，那么此时所有在call stack上的节点都可以到达这个环，所以是没有办法到达safe states的；反过来，如果能到达的所有点没有一个在环上，说明是可行的，是可以到达safe states的。时间复杂度O(V + E)，代码如下：



另外一个方法是运用拓扑排序，我们知道拓扑排序是会先收集所有indegree为0的点，然后删除所有这些点的出向边，一直循环知道没有这样的点为止。然而这道题是要找outdegree为0的点，然后删除入向边然后继续。但是我们只要把有向图的边全部反过来，在跑拓扑排序的话找到的就是实际上我们要找的点。时间复杂度同样是O(V+ E)，代码如下：