Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一幅有向图,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



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理