1857. Largest Color Value in a Directed Graph

[mah-shamim]

Topics: Hash Table, Dynamic Programming, Graph, Topological Sort, Memoization, Counting

There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.

You are given a string colors where colors[i] is a lowercase English letter representing the color of the ith node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [aj, bj] indicates that there is a directed edge from node aj to node bj.

A valid path in the graph is a sequence of nodes x1 -> x2 -> x3 -> ... -> xk such that there is a directed edge from xi to xi+1 for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Example 1:

• Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
• Output: 3
• Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).

Example 2:

• Input: colors = "a", edges = [[0,0]]
• Output: -1
• Explanation: There is a cycle from 0 to 0.

Constraints:

• n == colors.length
• m == edges.length
• 1 <= n <= 105
• 0 <= m <= 105
• colors consists of lowercase English letters.
• 0 <= aj, bj < n

Hint:

1. Use topological sort.
2. let dp[u][c] := the maximum count of vertices with color c of any path starting from vertex u. (by JerryJin2905)

[mah-shamim]

We need to determine the largest color value in a directed graph, considering possible cycles. If the graph contains a cycle, we return -1. Otherwise, we compute the maximum color value using dynamic programming combined with topological sorting.

Approach

1. Cycle Detection and Topological Sort: Use Kahn's algorithm to perform a topological sort. If the number of processed nodes is less than the total nodes, the graph contains a cycle, and we return -1.
2. Dynamic Programming (DP): For each node processed in topological order, maintain a DP array where dp[u][c] represents the maximum count of color c in any path ending at node u.
3. Reverse Adjacency List: Track predecessors for each node to efficiently update DP values based on incoming edges.
4. Color Count Update: For each node, initialize its DP array with its own color count. Then, update the DP values by considering all paths from predecessors, incrementing the count if the current node's color matches.

Let's implement this solution in PHP: 1857. Largest Color Value in a Directed Graph

<?php
/**
 * @param String $colors
 * @param Integer[][] $edges
 * @return Integer
 */
function largestPathValue($colors, $edges) {
    $n = strlen($colors);
    $m = count($edges);

    $reverse_adj = array_fill(0, $n, array());
    $original_adj = array_fill(0, $n, array());
    $in_degree = array_fill(0, $n, 0);

    foreach ($edges as $edge) {
        $a = $edge[0];
        $b = $edge[1];
        $original_adj[$a][] = $b;
        $reverse_adj[$b][] = $a;
        $in_degree[$b]++;
    }

    $queue = new SplQueue();
    $top_order = array();

    for ($i = 0; $i < $n; $i++) {
        if ($in_degree[$i] == 0) {
            $queue->enqueue($i);
        }
    }

    while (!$queue->isEmpty()) {
        $u = $queue->dequeue();
        $top_order[] = $u;
        foreach ($original_adj[$u] as $v) {
            $in_degree[$v]--;
            if ($in_degree[$v] == 0) {
                $queue->enqueue($v);
            }
        }
    }

    if (count($top_order) != $n) {
        return -1;
    }

    $dp = array();
    $max_color = 0;

    foreach ($top_order as $u) {
        $color = $colors[$u];
        $color_index = ord($color) - ord('a');
        $current_dp = array_fill(0, 26, 0);
        $current_dp[$color_index] = 1;

        foreach ($reverse_adj[$u] as $v) {
            for ($c = 0; $c < 26; $c++) {
                $temp = $dp[$v][$c] + ($color_index == $c ? 1 : 0);
                if ($temp > $current_dp[$c]) {
                    $current_dp[$c] = $temp;
                }
            }
        }

        $current_max = max($current_dp);
        if ($current_max > $max_color) {
            $max_color = $current_max;
        }
        $dp[$u] = $current_dp;
    }

    return $max_color;
}

$colors = "abaca";
$edges = [[0,1],[0,2],[2,3],[3,4]];
echo largestPathValue($colors, $edges);  // Output: 3

$colors = "a";
$edges = [[0,0]];
echo largestPathValue($colors, $edges);  // Output: -1
?>

Explanation:

1. Topological Sorting: Using Kahn's algorithm, we process nodes in a topological order. This ensures that each node is processed only after all its predecessors have been processed, which is crucial for correctly updating DP values.
2. Cycle Detection: If the topological sort processes fewer nodes than the total nodes, a cycle exists, and we return -1.
3. DP Initialization: Each node starts with a DP array initialized to 0 except for its own color, which is set to 1.
4. Updating DP Values: For each node, we update its DP array by considering all incoming edges (predecessors). For each predecessor, we check all color counts and update the current node's DP values to reflect the maximum possible counts from all paths ending at the current node.
5. Result Calculation: The maximum value in the DP array for each node is tracked to determine the largest color value in any valid path.

This approach efficiently combines topological sorting and dynamic programming to solve the problem in linear time relative to the number of edges and nodes, making it suitable for large input sizes.

[kovatz]

Thanks for solving the problem of "Largest Color Value in a Directed Graph"

[mah-shamim]

Thanks