【leetcode】802. Find Eventual Safe States

题目如下：

解题思路：本题大多数人采用DFS的方法，这里我用的是另一种方法。我的思路是建立一次初始值为空的safe数组，然后遍历graph，找到graph[i]中所有元素都在safe中的元素，把i加入safe。遍历完graph后继续重头遍历，直到某一次遍历后无新元素加入safe后停止。safe即为题目要求的答案。以上面例子距离，首先safe是空，第一次遍历graph后，safe=[5,6];第二次遍历后将2和4加入safe；第三次遍历后无新元素加入，safe最终结果为[5,6,2,4]

代码如下：

class Solution(object):

    def eventualSafeNodes(self, graph):

        """

        :type graph: List[List[int]]

        :rtype: List[int]

        """

        safe = []

        flag = True

        dic = {}

        while flag:

            flag = False

            for i,v in enumerate(graph):

                exist = True

                for j in v:

                    if j not in dic:

                        exist = False

                        break

                if exist == True and i not in dic:

                    safe.append(i)

                    dic[i] = 1

                    flag = True

        safe.sort()

        return safe

巴特西

【leetcode】802. Find Eventual Safe States

最新文章

热门文章