Re: [閒聊] 每日leetcode
看板Marginalman作者DJYOMIYAHINA (通通打死)時間10月前 (2025/01/24 23:23)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1304/1552 (看更多)
在下幾百年沒寫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
推
01/24 23:26,
10月前
, 1F
01/24 23:26, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1304 之 1552 篇)：