給定一個(gè)有向圖，和其中每個(gè)節(jié)點(diǎn)的顏色，問(wèn)其中的所有path中經(jīng)過(guò)同色最多的節(jié)點(diǎn)的個(gè)數(shù)，DFS劃水過(guò)了
*有部分參考->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