以下是 LeetCode 2876 「有向图访问计数」的 C 语言实现。核心思路为拓扑排序 反向 BFS时间复杂度 O(n)空间复杂度 O(n)。c#include stdlib.h#include string.h/*** Note: The returned array must be malloced, assume caller calls free().*/int* countVisitedNodes(int* edges, int edgesSize, int* returnSize) {int n edgesSize;int* ans (int*)calloc(n, sizeof(int));*returnSize n;// 1. 统计入度int* indeg (int*)calloc(n, sizeof(int));for (int i 0; i n; i) {indeg[edges[i]];}// 2. 拓扑排序移除所有树枝节点入度为 0 的节点int* queue (int*)malloc(n * sizeof(int));int head 0, tail 0;for (int i 0; i n; i) {if (indeg[i] 0) {queue[tail] i;}}while (head tail) {int u queue[head];int v edges[u];indeg[v]--;if (indeg[v] 0) {queue[tail] v;}}free(queue);// 3. 处理所有环计算环上节点的答案// 此时 indeg[i] 0 的节点一定在环上for (int i 0; i n; i) {if (indeg[i] 0 ans[i] 0) {// 收集当前环上的所有节点int* cycle (int*)malloc(n * sizeof(int));int cnt 0;int cur i;while (indeg[cur] 0) {cycle[cnt] cur;indeg[cur] -1; // 标记已处理cur edges[cur];}int len cnt;for (int j 0; j cnt; j) {ans[cycle[j]] len;}free(cycle);}}free(indeg);// 4. 构建反向图每个节点的所有前驱int** rg (int**)malloc(n * sizeof(int*));int* prevCnt (int*)calloc(n, sizeof(int));// 统计每个节点的前驱数量for (int i 0; i n; i) {prevCnt[edges[i]];}for (int i 0; i n; i) {rg[i] (int*)malloc(prevCnt[i] * sizeof(int));prevCnt[i] 0; // 复用为当前填充下标}for (int i 0; i n; i) {int to edges[i];rg[to][prevCnt[to]] i;}// 5. BFS 从环上节点向外更新树枝节点int* q (int*)malloc(n * sizeof(int));head 0, tail 0;for (int i 0; i n; i) {if (ans[i] 0) { // 环上节点q[tail] i;}}while (head tail) {int u q[head];for (int j 0; j prevCnt[u]; j) {int v rg[u][j];if (ans[v] 0) {ans[v] ans[u] 1;q[tail] v;}}}free(q);for (int i 0; i n; i) free(rg[i]);free(rg);free(prevCnt);return ans;}代码说明1. 入度统计每个节点指向 edges[i]因此目标节点的入度加一。2. 拓扑排序将所有入度为 0 的节点入队删除它们将其指向的节点入度减 1直到队列为空。此时剩余 indeg[i] 0 的节点都在环上。3. 环处理遍历所有节点若 indeg[i] 0 且 ans[i] 0则沿着 edges 收集整个环环长即为答案。4. 反向图构建为每个节点记录它的所有前驱节点用于从环向外传播答案。5. BFS 传播将环上节点作为起点不断向它的前驱节点传播答案ans[prev] ans[cur] 1直到所有节点被填充。复杂度分析· 时间复杂度O(n)每个节点和每条边都只被处理常数次。· 空间复杂度O(n)用于存储入度、队列、反向图等。