这道题（2876. 有向图访问计数）的核心在于识别出其图结构的特殊性：它是一个基环树（内向基环森林）。今天主要聊聊如何高效求解。
🎯 问题背景
题目给定长度为n的数组edges，其中 edges[i] 表示节点i有一条到节点edges[i]的有向边。也就是说，每个节点都有且只有一条出边。这种结构保证了从任意节点出发，最终一定会进入一个环。
结果是一个长度为n的数组 ans，ans[i] 代表从节点 i 出发，按照上述规则能访问的不同节点数。
💡 解题思路
面对这类问题，主要思路是利用拓扑排序找出所有环，再通过反向图来更新不在环上的节点的答案。
1. 找出所有环：因为出度都是1，可以通过拓扑排序层层剥离入度为0的节点（即“树枝”节点），剩下的就是所有在环上的节点。这些环上的节点各自的答案就是它们所在环的长度。
2. 处理环上的节点：对于每个环，其上的所有节点，能访问到的不同节点数就是环的长度。
3. 处理环外节点：对于不在环上的节点（“树枝”节点），它们通过唯一出边最终会进入某个环。它的答案是“它到环的路径长度 + 环的长度”。因此，我们需要构建原图的反向图，从环上的节点开始反向BFS，计算沿途节点的距离，并更新答案。
🧩 Java实现
以下是使用了拓扑排序和BFS的完整Java代码：
```java
public class Solution {
public int[] countVisitedNodes(List<Integer> edges) {
int n = edges.size();
int[] e = new int[n];
for (int i = 0; i < n; i++) {
e[i] = edges.get(i);
}
// 1. 统计入度
int[] indeg = new int[n];
for (int i = 0; i < n; i++) {
indeg[e[i]]++;
}
// 2. 拓扑排序，移除所有不在环上的节点（树枝）
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) {
q.add(i);
}
}
while (!q.isEmpty()) {
int u = q.poll();
int v = e[u];
indeg[v]–;
if (indeg[v] == 0) {
q.add(v);
}
}
// 3. 计算答案，此时 indeg[i] > 0 的节点一定在环上
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
if (indeg[i] <= 0) continue;
// 计算当前环的长度
List<Integer> cycle = new ArrayList<>();
int j = i;
while (indeg[j] > 0) {
cycle.add(j);
indeg[j] = -1; // 标记，避免重复处理
j = e[j];
}
int len = cycle.size();
// 环上所有节点的答案都是环的长度
for (int node : cycle) {
ans[node] = len;
}
}
// 4. 构建反向图，从环上的节点开始BFS，更新树枝节点的答案
List<Integer>[] rg = new List[n];
for (int i = 0; i < n; i++) {
rg[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
rg[e[i]].add(i);
}
// 从所有环上节点开始，进行 BFS 或 DFS 更新树枝
for (int i = 0; i < n; i++) {
if (ans[i] > 0) {
Deque<int[]> dq = new ArrayDeque<>();
dq.add(new int[]{i, 1}); // 节点、距离
while (!dq.isEmpty()) {
int[] cur = dq.poll();
int u = cur[0];
int dist = cur[1];
for (int v : rg[u]) {
if (ans[v] == 0) {
ans[v] = ans[u] + dist;
dq.add(new int[]{v, dist + 1});
}
}
}
}
}
return ans;
}
}
```
🌟 另一种理解：DFS + 时间戳
LeetCode 官方也提供了一种基于DFS的思路，使用时间戳来识别环，同样可以在O(n)时间内解决。
```java
public class Solution {
public int[] countVisitedNodes(List<Integer> edges) {
int n = edges.size();
int[] e = new int[n];
for (int i = 0; i < n; i++) {
e[i] = edges.get(i);
}
int[] ans = new int[n];
int[] vis = new int[n]; // 0:未访问, 1:访问中, 2:已处理
for (int i = 0; i < n; i++) {
if (vis[i] == 0) {
dfs(i, e, ans, vis);
}
}
return ans;
}
private int dfs(int u, int[] e, int[] ans, int[] vis) {
if (ans[u] != 0) {
return ans[u];
}
if (vis[u] == 1) {
// 发现环
int size = 1;
int v = e[u];
while (v != u) {
size++;
v = e[v];
}
v = u;
while (ans[v] == 0) {
ans[v] = size;
v = e[v];
}
return size;
}
if (vis[u] == 2) {
return ans[u];
}
vis[u] = 1;
int nxt = e[u];
int res = dfs(nxt, e, ans, vis);
if (ans[u] == 0) {
ans[u] = res + 1;
}
vis[u] = 2;
return ans[u];
}
}
```
—
⚙️ 复杂度分析
两种解法的时间复杂度都是O(n)，空间复杂度也都是O(n)。在n最大为10^5的约束下，性能完全没有问题。
如果对其中某个步骤的细节有疑问，比如如何进行拓扑排序或反向图的构建，我们可以继续深入讨论。
