Re: [閒聊] 每日leetcode

[DJYOMIYAHINA (通通打死)]

在下幾百年沒寫DFS了
狗屎一般的寫法
早用拓ㄆ排序

def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:

    n = len(graph)
    flag = [1 if len(graph[i])==0 else 0 for i in range(n)]

    visited = [0 for _ in range(n)]
    def dfs(cur) -> int:
        if flag[cur] != 0:
            return flag[cur]
        if visited[cur] == 1:
            flag[cur] = -1
            return flag[cur]

        visited[cur] = 1
        cur_traversal = []
        for node in graph[cur]:
            cur_traversal.append(dfs(node))

        if all([f==1 for f in cur_traversal]):
            flag[cur] = 1
            return 1
        if any([f==-1 for f in cur_traversal]):
            flag[cur] = -1
            return -1
        return 2

    ans = []
    for i in range(n):
        if dfs(i)==1:
            ans.append(i)
    return ans

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737732198.A.4BD.html
推 HGK: 資料結構