现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 1 。此外，该图还包含了 n 条有向边。
给你一个下标从 0 开始的数组 edges ，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。
你从节点 x 开始，通过边访问其他节点，直到你在此过程中再次访问到之前已经访问过的节点。
返回数组 answer 作为答案，其中 answer[i] 表示如果从节点 i 开始执行该过程，你可以访问到的不同节点数
一. 快慢指针 + 反向建图
class Solution {
public:
vector<int> countVisitedNodes(vector<int>& fa) {
int n = fa.size();
vector<int> ans(n), vis(n);
vector<vector<int>> g(n);
for (int i = 0; i < n; i++) g[fa[i]].emplace_back(i); // 反向建图
for (int t = 0; t < n; t++) {
if (vis[t] == 1) continue;
int l = t, r = t, s = 0;
queue<int> q = queue<int>();
do { l = fa[l], r = fa[fa[r]]; } while (l != r);
do { l = fa[l], r = fa[fa[r]], s++; } while (l != r);
do { l = fa[l], r = fa[fa[r]], ans[l] = s, vis[l] = 1, q.push(l); } while (l != r);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto& v: g[u]) {
if (vis[v] == 1) continue;
ans[v] = ans[u] + 1, vis[v] = 1; q.push(v);
}
}
}
return ans;
}
};
二. 拓扑排序 + 基环树
class Solution {
public:
vector<int> countVisitedNodes(vector<int> &g) {
int n = g.size();
vector<vector<int>> rg(n); // 反图
vector<int> deg(n);
for (int x = 0; x < n; x++) {//建立反图和入度表
int y = g[x];
rg[y].push_back(x);
deg[y]++;
}
// 拓扑排序，剪掉 g 上的所有树枝
// 拓扑排序后，deg 值为 1 的点必定在基环上，为 0 的点必定在树枝上
queue<int> q;
for (int i = 0; i < n; i++)
if (deg[i] == 0) q.push(i);
while (!q.empty()) {
int x = q.front(); q.pop();
int y = g[x];
if (--deg[y] == 0) q.push(y);
}
vector<int> ans(n, 0);
// 在反图上遍历树枝
function<void(int, int)> rdfs = [&](int x, int depth) {
ans[x] = depth;
for (int y: rg[x]) {
if (deg[y] == 0) // 避免访问基环
rdfs(y, depth + 1);
}
};
for (int i = 0; i < n; i++) {
if (deg[i] < 1) continue;
vector<int> ring;
for (int x = i;; x = g[x]) { //遍历基环
deg[x] = -1; // 将基环上的点的入度标记为 -1，避免重复访问，当做vis使用
ring.push_back(x); // 收集在基环上的点
if (g[x] == i) break;
}
for (int x: ring) //
rdfs(x, ring.size()); // 为方便计算，以 ring.size() 作为初始深度
}
return ans;
}
};