DeepSeek LeetCode 2876. 有向图访问计数 C语言实现

以下是 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)，用于存储入度、队列、反向图等。