题目描述
给你一个 有向图,它含有 n
个节点和 m
条边。节点编号从 0
到 n - 1
。
给你一个字符串 colors
,其中 colors[i]
是小写英文字母,表示图中第 i
个节点的 颜色(下标从 0
开始)。同时给你一个二维数组 edges
,其中 edges[j] = [a_j, b_j]
表示从节点 a_j
到节点 b_j
有一条 有向边。
图中一条有效 路径 是一个点序列 x_1 -> x_2 -> x_3 -> ... -> x_k
,对于所有 1 <= i < k
,从 x_i
到 x_i+1
在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。
请你返回给定图中有效路径里面的 最大颜色值。如果图中含有环,请返回 -1
。
样例
输入:colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
输出:3
解释:路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 "a" 的节点(上图中的红色节点)。
输入:colors = "a", edges = [[0,0]]
输出:-1
解释:从 0 到 0 有一个环。
限制
n == colors.length
m == edges.length
1 <= n <= 10^5
0 <= m <= 10^5
colors
只含有小写英文字母。0 <= a_j, b_j < n
算法
(拓扑排序) $O(n + m)$
- 求出每个点的入度,进行拓扑排序。
- 每个点维护一个长度为 26 的数组,记录每个字母从任意起点到当前点的出现次数。
时间复杂度
- 拓扑排序的每次更新时间复杂度为常数,故总时间复杂度为 $O(n + m)$。
空间复杂度
- 需要 $O(n + m)$ 的额外空间存储邻接表,队列和其他数据结构。
C++ 代码
class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges) {
const int n = colors.size();
vector<vector<int>> graph(n);
vector<int> indeg(n, 0);
for (const auto &e : edges) {
graph[e[0]].push_back(e[1]);
indeg[e[1]]++;
}
int ans = 1;
queue<int> q;
vector<vector<int>> m(n, vector<int>(26, 0));
for (int i = 0; i < n; i++)
if (indeg[i] == 0) {
q.push(i);
m[i][colors[i] - 'a']++;
}
int counter = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
counter++;
for (int v : graph[u]) {
indeg[v]--;
if (indeg[v] == 0)
q.push(v);
for (int j = 0; j < 26; j++) {
m[v][j] = max(m[v][j], m[u][j] + (colors[v] - 'a' == j));
ans = max(ans, m[v][j]);
}
}
}
if (counter < n)
return -1;
return ans;
}
};