Largest Color Value in a Directed Graph ↗

• Idea: 用 Kahn 演算法做拓撲排序，同時用 DP 陣列追蹤每種顏色的最大出現次數
• Time: O((V + E) * 26)
• Space: O(V * 26)

class Solution {
    fun largestPathValue(colors: String, edges: Array<IntArray>): Int {
        val n = colors.length
        val graph = Array(n) { mutableListOf<Int>() }
        val inDeg = IntArray(n)

        for ((u, v) in edges) {
            graph[u].add(v)
            inDeg[v]++
        }

        // dp[node][color] = 到達 node 的路徑中 color 的最大出現次數
        val dp = Array(n) { IntArray(26) }
        val queue = ArrayDeque<Int>()

        for (i in 0 until n) {
            if (inDeg[i] == 0) queue.add(i)
        }

        var processed = 0
        var result = 0

        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            processed++
            dp[node][colors[node] - 'a']++
            result = maxOf(result, dp[node][colors[node] - 'a'])

            for (next in graph[node]) {
                for (c in 0 until 26) {
                    dp[next][c] = maxOf(dp[next][c], dp[node][c])
                }
                inDeg[next]--
                if (inDeg[next] == 0) queue.add(next)
            }
        }

        return if (processed == n) result else -1
    }
}

• Idea: DFS 後序遍歷，用三色標記偵測環，同時計算每個節點的顏色計數
• Time: O((V + E) * 26)
• Space: O(V * 26)

class Solution {
    fun largestPathValue(colors: String, edges: Array<IntArray>): Int {
        val n = colors.length
        val graph = Array(n) { mutableListOf<Int>() }
        for ((u, v) in edges) graph[u].add(v)

        val dp = Array(n) { IntArray(26) { -1 } }
        val state = IntArray(n) // 0: 未訪問, 1: 處理中, 2: 完成
        var result = 0

        fun dfs(node: Int): Boolean {
            if (state[node] == 1) return false // 環
            if (state[node] == 2) return true
            state[node] = 1
            dp[node] = IntArray(26)

            for (next in graph[node]) {
                if (!dfs(next)) return false
                for (c in 0 until 26) {
                    dp[node][c] = maxOf(dp[node][c], dp[next][c])
                }
            }

            dp[node][colors[node] - 'a']++
            result = maxOf(result, dp[node][colors[node] - 'a'])
            state[node] = 2
            return true
        }

        for (i in 0 until n) {
            if (state[i] == 0 && !dfs(i)) return -1
        }
        return result
    }
}