Largest Color Value in a Directed Graph LeetCode solution in Python

1
class Graph:
2

3
    def __init__(self, colors):
4
        self.V = len(colors)
5
        self.adj = [[] for _ in range(self.V)]
6
        self.reset()
7

8
    def reset(self):
9
        self.visited = [False] * self.V
10
        self.recursion = [False] * self.V
11
        self.stack = []
12

13
    def addEdges(self, edges: List[List[int]]):
14
        for u, v in edges:
15
            self.addEdge(u, v)
16

17
    def addEdge(self, u, v):
18
        self.adj[u].append(v)
19

20
    def DFS(self, u):
21
        if self.recursion[u]:
22
            raise ValueError("Cycled Detected")
23

24
        if self.visited[u]:
25
            return
26

27
        self.visited[u] = True
28
        self.recursion[u] = True
29

30
        for v in self.adj[u]:
31
            self.DFS(v)
32

33
        self.stack.append(u)
34

35
        self.recursion[u] = False
36

37
    def getTopologicalSortOrder(self):
38
        self.reset()
39

40
        for u in range(self.V):
41
            self.DFS(u)
42

43
        return self.stack[::-1]
44

45
    def isConnected(self, u, v):
46
        return self.adj[u].index(v) >= 0
47

48
    def getAdjs(self, u):
49
        return self.adj[u]
50

51

52
class Solution:
53
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
54

55
        g = Graph(colors)
56
        g.addEdges(edges)
57

58
        try:
59
            order = g.getTopologicalSortOrder()
60

61
            result, dp = 0, [[0] * 26 for _ in range(len(order) + 1)]
62
            for i in range(len(order) - 1, -1, -1):
63
                u = order[i]
64
                # we are storing the max colours possible for all paths from this node
65
                for v in g.getAdjs(u):
66
                    for k in range(26):
67
                        dp[u][k] = max(dp[u][k], dp[v][k])
68

69
                c = ord(colors[u]) - 97
70
                dp[u][c] += 1
71

72
                result = max(result, max(dp[u]))
73

74
            return result
75
        except:
76
            return -1