Leetcode 2876. Count Visited Nodes in a Directed Graph

[Woodyiiiiiii]

2876. Count Visited Nodes in a Directed Graph

2876. Count Visited Nodes in a Directed Graph

题解：
【模板】内向基环树，附题单（Python/Java/C++/Go）

类似题目：
2127. Maximum Employees to Be Invited to a Meeting
2360. Longest Cycle in a Graph

分析题目条件，n个点n条边，说明肯定有环，而且每个点只有一个出度，所以相当于环上有指向其的树枝，总之，这是内向基环树的模型。

这种模型，常见的方法是用拓扑排序区分环和树枝，先用拓扑排序记录入度，然后得到环上的点，接着遍历环上的点用反图去遍历树枝上的点。

class Solution {
    public int[] countVisitedNodes(List<Integer> edges) {
        int n = edges.size();
        int[] ans = new int[n];
        int[] inDeg = new int[n];
        Map<Integer, Set<Integer>> reg = new HashMap<>();
        for (int i = 0; i < n; i++) {
            reg.computeIfAbsent(edges.get(i), k -> new HashSet<>()).add(i);
            inDeg[edges.get(i)]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDeg[i] == 0) {
                q.add(i);
            }
        }
        while (!q.isEmpty()) {
            int cur = q.poll();
            int next = edges.get(cur);
            inDeg[next]--;
            if (inDeg[next] == 0) {
                q.add(next);
            }
        }

        for (int i = 0; i < n; i++) {
            if (inDeg[i] <= 0) {
                continue;
            }
            List<Integer> ring = new ArrayList<>();
            for (int x = i; ; x = edges.get(x)) {
                ring.add(x);
                inDeg[x] = -1;
                if (edges.get(x) == i) {
                    break;
                }
            }
            for (int x : ring) {
                rDfs(x, ring.size(), reg, ans, inDeg);
            }
        }

        return ans;
    }

    private void rDfs(int cur, int depth, final Map<Integer, Set<Integer>> reg, int[] ans, final int[] inDeg) {
        ans[cur] = depth;
        for (int x : reg.getOrDefault(cur, new HashSet<>())) {
            if (inDeg[x] == 0) {
                rDfs(x, depth + 1, reg, ans, inDeg);
            }
        }
    }
}