Leetcode 802 Find Eventual Safe States

发表于 |

description

分析：
这道题是要在一个图里找不在环路中的节点，显然，dfs遍历即可，不过这里用拓扑排序方法也可以做，因为dfs这个方法我掌握得还不太熟练，老出各种小错误，等我钻研更深之后再补上dfs方法

思路：
记录下每个节点的出度，如果出度为0那必然是环路外的节点，然后将该点以及指向该点的边删除，继续寻找出度为0的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def eventualSafeNodes(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[int]
        """
        if not graph: return []

        n = len(graph)
        # 用字段存储每个节点的父节点
        d = {u:[] for u in range(n)}
        degree = [0] * n
        for u in range(n):
            for v in graph[u]:
                d[v].append(u)
            degree[u] = len(graph[u])

        Q = [u for u in range(n) if degree[u]==0]
        res = []
        while Q:
            node = Q.pop()
            res.append(node)
            for nodes in d[node]:
                degree[nodes] -= 1
                if degree[nodes] == 0:
                    Q.append(nodes)
        return sorted(res)