Posted on 2023-03-26 18:35
Uriel 閱讀(36)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
圖論 、
閑來無事重切Leet Code
給出一幅有向圖，edges每一個元素edges[i]代表從節(jié)點i可以到達edges[i]（從每個節(jié)點出發(fā)最多只有一條邊，edges[i]=-1代表從該點沒有向外的邊），問圖中最大的環(huán)包含多少節(jié)點，簡單DFS即可
1 #2360
2 #Runtime: 1406 ms (Beats 28.57%)
3 #Memory: 135.2 MB (Beats 14.29%)
4
5 class Solution(object):
6 def longestCycle(self, edges):
7 """
8 :type edges: List[int]
9 :rtype: int
10 """
11 vis = [0] * len(edges)
12 self.ans = -1
13 self.pre = 0
14 def DFS(node, st):
15 self.pre += 1
16 vis[node] = self.pre
17 if edges[node] == -1:
18 return
19 if not vis[edges[node]]:
20 DFS(edges[node], st)
21 elif vis[edges[node]] > st:
22 self.ans = max(self.ans, self.pre - vis[edges[node]] + 1)
23 for i in range(len(edges)):
24 if not vis[i]:
25 DFS(i, self.pre)
26 return self.ans