Posted on 2023-03-26 18:35
Uriel 阅读(16)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
图论 、
闲来无事重切Leet Code
给出一幅有向图，edges每一个元素edges[i]代表从节点i可以到达edges[i]（从每个节点出发最多只有一条边，edges[i]=-1代表从该点没有向外的边），问图中最大的环包含多少节点，简单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