KK's blog

每天积累多一些

0%

LeetCode 1857 Largest Color Value in a Directed Graph

Posted on Edited on Disqus:

LeetCode



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 i<sup>th</sup> node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [a<sub>j</sub>, b<sub>j</sub>] indicates that there is a directed edge from node a<sub>j</sub> to node b<sub>j</sub>.

A valid path in the graph is a sequence of nodes x<sub>1</sub> -> x<sub>2</sub> -> x<sub>3</sub> -> ... -> x<sub>k</sub> such that there is a directed edge from x<sub>i</sub> to x<sub>i+1</sub> 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 <= 10<sup>5</sup> 0 <= m <= 10<sup>5</sup>
colors consists of lowercase English letters. 0 <= a<sub>j</sub>, b<sub>j</sub> < n

题目大意：

给定一个图，有n个节点，每个节点的颜色已知，用a-z表示，求所有不循环路径上同种颜色的最大节点数，若有循环返回-1.

算法思路：

拓扑排序 + DP

  1. 看到侦测循环考虑用拓扑排序
  2. 拓扑排序的同时，如果知道父亲节点有最大的同种颜色数，容易计算儿子的同种颜色数dp[child]
    dp[child] = max(dp[parent]) for all the parents for the child
    由于有26种颜色，扩展到最大的第i种颜色数dp[child][i]表示以child为结尾的路径上第i种颜色的累计最大节点数 
    1
    2
    dp[child][i] = max(dp[parent][i] + 1) if color[child] == color[parent] for all the immediate parents for the child, i = 1..26 
    			= max(dp[parent][i])     if color[child] != color[parent]

注意事项：

  1. 见到最值且跟图相关，就考虑用BFS，而且要侦测循环就要用拓扑排序。要记录父节点颜色的累计和，考虑用DP，DP跟颜色相关且颜色都是小写字母，也就是26种
  2. 递归式是所有直接父节点的最大值。因为若有两条路径到达child这个节点，路径1第a种颜色有2个，而路径上第a种颜色有5个。
  3. 计算dp值在知道边的始点和终点上，也就是入度数减一之前。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
	graph = [[] for _ in range(len(colors))]
	in_degree = [0] * len(colors)
	for _edge in edges:
		graph[_edge[0]].append(_edge[1])
		in_degree[_edge[1]] += 1
	res = []
	dp = [[0 for _ in range(26)] for _ in range(len(colors))]
	initial_nodes = [i for i in range(len(in_degree)) if in_degree[i] == 0]
	for _node in initial_nodes:
		dp[_node][ord(colors[_node]) - ord('a')] = 1
	queue = collections.deque(initial_nodes)
	while queue:
		node = queue.popleft()
		res.append(node)
		for j in graph[node]:
			for i in range(26):
				dp[j][i] = max(dp[j][i], dp[node][i] + (1 if ord(colors[j]) - ord('a') == i else 0)) # remember max(dp[j][i]
			in_degree[j] -= 1
			if in_degree[j] == 0:
				queue.append(j)
	return -1 if len(colors) != len(res) else max(map(max, dp))

算法分析：

时间复杂度为O(V + E)，空间复杂度O(V + E)

Free mock interview