这道题2876. 有向图访问计数的核心在于识别出其图结构的特殊性它是一个基环树内向基环森林。今天主要聊聊如何高效求解。 问题背景题目给定长度为n的数组edges其中 edges[i] 表示节点i有一条到节点edges[i]的有向边。也就是说每个节点都有且只有一条出边。这种结构保证了从任意节点出发最终一定会进入一个环。结果是一个长度为n的数组 ansans[i] 代表从节点 i 出发按照上述规则能访问的不同节点数。 解题思路面对这类问题主要思路是利用拓扑排序找出所有环再通过反向图来更新不在环上的节点的答案。1. 找出所有环因为出度都是1可以通过拓扑排序层层剥离入度为0的节点即“树枝”节点剩下的就是所有在环上的节点。这些环上的节点各自的答案就是它们所在环的长度。2. 处理环上的节点对于每个环其上的所有节点能访问到的不同节点数就是环的长度。3. 处理环外节点对于不在环上的节点“树枝”节点它们通过唯一出边最终会进入某个环。它的答案是“它到环的路径长度 环的长度”。因此我们需要构建原图的反向图从环上的节点开始反向BFS计算沿途节点的距离并更新答案。 Java实现以下是使用了拓扑排序和BFS的完整Java代码javapublic class Solution {public int[] countVisitedNodes(ListInteger 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. 拓扑排序移除所有不在环上的节点树枝DequeInteger 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;// 计算当前环的长度ListInteger 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更新树枝节点的答案ListInteger[] 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) {Dequeint[] 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)时间内解决。javapublic class Solution {public int[] countVisitedNodes(ListInteger 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的约束下性能完全没有问题。如果对其中某个步骤的细节有疑问比如如何进行拓扑排序或反向图的构建我们可以继续深入讨论。