题目描述
现有一个有向图,其中包含 n
个节点,节点编号从 0
到 n - 1
。此外,该图还包含了 n
条有向边。
给你一个下标从 0 开始的数组 edges
,其中 edges[i]
表示存在一条从节点 i
到节点 edges[i]
的边。
想象在图上发生以下过程:
- 你从节点
x
开始,通过边访问其他节点,直到你在 此过程 中再次访问到之前已经访问过的节点。
返回数组 answer
作为答案,其中 answer[i]
表示如果从节点 i
开始执行该过程,你可以访问到的不同节点数。
样例
输入:edges = [1,2,0,0]
输出:[3,3,3,4]
解释:从每个节点开始执行该过程,记录如下:
- 从节点 0 开始,访问节点 0 -> 1 -> 2 -> 0。访问的不同节点数是 3。
- 从节点 1 开始,访问节点 1 -> 2 -> 0 -> 1。访问的不同节点数是 3。
- 从节点 2 开始,访问节点 2 -> 0 -> 1 -> 2。访问的不同节点数是 3。
- 从节点 3 开始,访问节点 3 -> 0 -> 1 -> 2 -> 0。访问的不同节点数是 4。
输入:edges = [1,2,3,4,0]
输出:[5,5,5,5,5]
解释:无论从哪个节点开始,在这个过程中,都可以访问到图中的每一个节点。
限制
n == edges.length
2 <= n <= 10^5
0 <= edges[i] <= n - 1
edges[i] != i
算法
(内向基环森林,拓扑排序,递归遍历) $O(n)$
- 这个图最终会形成若干个内向基环树,组成一个内向基环森林。在环上节点的答案就是这个连通块中基环的长度,在环外节点的答案是达到入环点的距离加上基环的长度。
- 通过拓扑排序求出环上的节点。
- 遍历每个环,并求出每个环上节点的答案(环的长度)。
- 从每个未被遍历过的节点开始递归遍历,如果下一个节点已经计算过了答案(无论是环内还是环外),则直接返回这个答案。否则继续递归遍历下一个节点,直到所有节点都被遍历过了一次。
时间复杂度
- 拓扑排序,遍历环以及递归遍历的时间复杂度都是 $O(n)$,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储入度、拓扑排序的队列、递归的系统栈空间和答案。
C++ 代码
class Solution {
private:
int n;
vector<int> indegs, ans;
void topsort(const vector<int> &edges) {
queue<int> q;
for (int i = 0; i < n; i++)
if (indegs[i] == 0)
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
if (--indegs[edges[u]] == 0)
q.push(edges[u]);
}
}
void init_loop_ans(const vector<int> &edges) {
for (int i = 0; i < n; i++) {
if (indegs[i] == 0 || ans[i] > 0)
continue;
vector<int> t;
int j = i;
do {
t.push_back(j);
j = edges[j];
} while (j != i);
for (int u : t)
ans[u] = t.size();
}
}
void dfs(int u, const vector<int> &edges) {
int v = edges[u];
if (ans[v] == 0)
dfs(v, edges);
ans[u] = ans[v] + 1;
}
public:
vector<int> countVisitedNodes(vector<int>& edges) {
n = edges.size();
indegs.resize(n, 0);
for (int i = 0; i < n; i++)
++indegs[edges[i]];
topsort(edges);
ans.resize(n, 0);
init_loop_ans(edges);
for (int i = 0; i < n; i++)
if (ans[i] == 0)
dfs(i, edges);
return ans;
}
};