1857. Largest Color Value in a Directed Graph - Explanation

class Solution:
    def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
        n = len(colors)
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)

        visit = [False] * n
        def dfs(node, c):
            if visit[node]:
                return float("inf")

            visit[node] = True
            clrCnt = 0
            for nei in adj[node]:
                cur = dfs(nei, c)
                if cur == float("inf"):
                    return cur
                clrCnt = max(clrCnt, cur)
            visit[node] = False
            return clrCnt + (c == (ord(colors[node]) - ord('a')))

        res = -1
        for i in range(n):
            for c in range(26):
                cnt = dfs(i, c)
                if cnt == float("inf"):
                    return -1
                res = max(res, cnt)
        return res

class Solution:
    def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
        adj = defaultdict(list)
        for src, dst in edges:
            adj[src].append(dst)

        def dfs(node):
            if node in path:
                return float("inf")
            if node in visit:
                return 0

            visit.add(node)
            path.add(node)
            colorIndex = ord(colors[node]) - ord('a')
            count[node][colorIndex] = 1

            for nei in adj[node]:
                if dfs(nei) == float("inf"):
                    return float("inf")
                for c in range(26):
                    count[node][c] = max(
                        count[node][c],
                        (1 if c == colorIndex else 0) + count[nei][c]
                    )

            path.remove(node)
            return 0

        n, res = len(colors), 0
        visit, path = set(), set()
        count = [[0] * 26 for _ in range(n)]

        for i in range(n):
            if dfs(i) == float("inf"):
                return -1
            res = max(res, max(count[i]))

        return res

class Solution:
    def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
        n = len(colors)
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        count = [[0] * 26 for _ in range(n)]

        for u, v in edges:
            adj[u].append(v)
            indegree[v] += 1

        q = deque()
        for i in range(n):
            if indegree[i] == 0:
                q.append(i)

        visit = res = 0
        while q:
            node = q.popleft()
            visit += 1
            colorIndex = ord(colors[node]) - ord('a')
            count[node][colorIndex] += 1
            res = max(res, count[node][colorIndex])

            for nei in adj[node]:
                for c in range(26):
                    count[nei][c] = max(count[nei][c], count[node][c])

                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)

        return res if visit == n else -1