Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一个有向图,和其中每个节点的颜色,问其中的所有path中经过同色最多的节点的个数,DFS划水过了
*有部分参考->https://leetcode.com/problems/largest-color-value-in-a-directed-graph/solutions/3396323/


 1 #1857
 2 #Runtime: 3256 ms (Beats 12.50%)
 3 #Memory: 202.1 MB (Beats 12.50%)
 4 
 5 class Solution(object):
 6     def largestPathValue(self, colors, edges):
 7         """
 8         :type colors: str
 9         :type edges: List[List[int]]
10         :rtype: int
11         """
12         graph = defaultdict(list)
13         for x, y in edges:
14             graph[x].append(y)
15         vis = set()
16         path = set()
17         ans = 0
18         n = len(colors)
19         self.has_circle = False
20         cnt = [[0] * 26 for _ in range(n)]
21         def DFS(x):
22             if x in path:
23                 self.has_circle = True
24             if x in vis:
25                 return 0
26             vis.add(x)
27             path.add(x)
28             idx = ord(colors[x]) - ord('a')
29             cnt[x][idx] = 1
30             for y in graph[x]:
31                 DFS(y)
32                 if self.has_circle == True:
33                     return float('inf')
34                 for ch in range(26):
35                     cnt[x][ch] = max(cnt[x][ch], (1 if ch == idx else 0) + cnt[y][ch])
36             path.remove(x)
37             return max(cnt[x])
38 
39         for i in range(n):
40             ans = max(ans, DFS(i))
41         return -1 if ans == float('inf'else ans

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