有向图访问计数

现有一个有向图，其中包含 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;
    }
};