2876. 统计有向图中被访问的节点数

Hard

题目描述

有一个由 n 个节点组成的有向图，节点编号从 0 到 n - 1，共有 n 条有向边。

给你一个下标从 0 开始的数组 edges，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。

考虑在图上进行以下过程：

你从节点 x 开始，通过边不断访问其他节点，直到你到达一个在这个过程中已经访问过的节点。

返回数组 answer，其中 answer[i] 是从节点 i 开始执行该过程时你将访问的不同节点数。

示例 1：

输入：edges = [1,2,0,0]
输出：[3,3,3,4]
解释：我们从每个节点开始执行该过程：
- 从节点 0 开始，访问节点 0 -> 1 -> 2 -> 0。访问的不同节点数为 3。
- 从节点 1 开始，访问节点 1 -> 2 -> 0 -> 1。访问的不同节点数为 3。
- 从节点 2 开始，访问节点 2 -> 0 -> 1 -> 2。访问的不同节点数为 3。
- 从节点 3 开始，访问节点 3 -> 0 -> 1 -> 2 -> 0。访问的不同节点数为 4。

示例 2：

输入：edges = [1,2,3,4,0]
输出：[5,5,5,5,5]
解释：从任何节点开始，都可以在该过程中访问图中的每个节点。

提示：

n == edges.length
2 <= n <= 10^5
0 <= edges[i] <= n - 1
edges[i] != i

解题思路

这是一个关于有向图环检测和路径统计的问题。由于每个节点都有且仅有一条出边，图的结构有特殊性质。

核心观察：

由于每个节点恰好有一条出边，从任意节点出发最终必定会进入一个环
图的结构可以看作若干个环加上指向这些环的树状结构

解法思路：

找环阶段：使用快慢指针或DFS找出所有的环，并标记环中的节点
计算环内节点答案：环内任意节点的答案都是环的大小
计算环外节点答案：对于不在环内的节点，它们最终会到达某个环，答案是到达环的步数加上环的大小

具体实现：

先遍历所有节点，找到所有环并记录环的大小
对于环内节点，直接设置答案为环大小
对于环外节点，从该节点开始走，直到遇到已知答案的节点（环内节点或已计算过的节点），然后反向计算路径上每个节点的答案

这种方法确保每个节点最多被访问常数次，时间复杂度为O(n)。

代码实现

class Solution {
public:
    vector<int> countVisitedNodes(vector<int>& edges) {
        int n = edges.size();
        vector<int> answer(n, -1);
        vector<bool> visited(n, false);
        vector<bool> inCycle(n, false);
        
        // 找环并计算环内节点的答案
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            
            // 使用快慢指针找环
            int slow = i, fast = i;
            do {
                slow = edges[slow];
                fast = edges[edges[fast]];
            } while (slow != fast);
            
            // 找到环的起点
            int cycleStart = i;
            while (cycleStart != slow) {
                cycleStart = edges[cycleStart];
                slow = edges[slow];
            }
            
            // 计算环的大小
            int cycleSize = 1;
            int curr = edges[cycleStart];
            while (curr != cycleStart) {
                curr = edges[curr];
                cycleSize++;
            }
            
            // 标记环中的节点并设置答案
            curr = cycleStart;
            do {
                inCycle[curr] = true;
                answer[curr] = cycleSize;
                visited[curr] = true;
                curr = edges[curr];
            } while (curr != cycleStart);
        }
        
        // 计算环外节点的答案
        function<int(int)> dfs = [&](int node) -> int {
            if (answer[node] != -1) return answer[node];
            answer[node] = dfs(edges[node]) + 1;
            return answer[node];
        };
        
        for (int i = 0; i < n; i++) {
            if (answer[i] == -1) {
                dfs(i);
            }
        }
        
        return answer;
    }
};

class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
        n = len(edges)
        answer = [-1] * n
        visited = [False] * n
        in_cycle = [False] * n
        
        # 找环并计算环内节点的答案
        for i in range(n):
            if visited[i]:
                continue
                
            # 使用快慢指针找环
            slow = fast = i
            while True:
                slow = edges[slow]
                fast = edges[edges[fast]]
                if slow == fast:
                    break
            
            # 找到环的起点
            cycle_start = i
            while cycle_start != slow:
                cycle_start = edges[cycle_start]
                slow = edges[slow]
            
            # 计算环的大小
            cycle_size = 1
            curr = edges[cycle_start]
            while curr != cycle_start:
                curr = edges[curr]
                cycle_size += 1
            
            # 标记环中的节点并设置答案
            curr = cycle_start
            while True:
                in_cycle[curr] = True
                answer[curr] = cycle_size
                visited[curr] = True
                curr = edges[curr]
                if curr == cycle_start:
                    break
        
        # 计算环外节点的答案
        def dfs(node):
            if answer[node] != -1:
                return answer[node]
            answer[node] = dfs(edges[node]) + 1
            return answer[node]
        
        for i in range(n):
            if answer[i] == -1:
                dfs(i)
        
        return answer

public class Solution {
    public int[] CountVisitedNodes(IList<int> edges) {
        int n = edges.Count;
        int[] answer = new int[n];
        bool[] visited = new bool[n];
        bool[] inCycle = new bool[n];
        
        for (int i = 0; i < n; i++) {
            answer[i] = -1;
        }
        
        // 找环并计算环内节点的答案
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            
            // 使用快慢指针找环
            int slow = i, fast = i;
            do {
                slow = edges[slow];
                fast = edges[edges[fast]];
            } while (slow != fast);
            
            // 找到环的起点
            int cycleStart = i;
            while (cycleStart != slow) {
                cycleStart = edges[cycleStart];
                slow = edges[slow];
            }
            
            // 计算环的大小
            int cycleSize = 1;
            int curr = edges[cycleStart];
            while (curr != cycleStart) {
                curr = edges[curr];
                cycleSize++;
            }
            
            // 标记环中的节点并设置答案
            curr = cycleStart;
            do {
                inCycle[curr] = true;
                answer[curr] = cycleSize;
                visited[curr] = true;
                curr = edges[curr];
            } while (curr != cycleStart);
        }
        
        // 计算环外节点的答案
        int Dfs(int node) {
            if (answer[node] != -1) return answer[node];
            answer[node] = Dfs(edges[node]) + 1;
            return answer[node];
        }
        
        for (int i = 0; i < n; i++) {
            if (answer[i] == -1) {
                Dfs(i);
            }
        }
        
        return answer;
    }
}

var countVisitedNodes = function(edges) {
    const n = edges.length;
    const answer = new Array(n).fill(-1);
    const visited = new Array(n).fill(false);
    const inCycle = new Array(n).fill(false);
    
    // 找环并计算环内节点的答案
    for (let i = 0; i < n; i++) {
        if (visited[i]) continue;
        
        // 使用快慢指针找环
        let slow = i, fast = i;
        do {
            slow = edges[slow];
            fast = edges[edges[fast]];
        } while (slow !== fast);
        
        // 找到环的起点
        let cycleStart = i;
        while (cycleStart !== slow) {
            cycleStart = edges[cycleStart];
            slow = edges[slow];
        }
        
        // 计算环的大小
        let cycleSize = 1;
        let curr = edges[cycleStart];
        while (curr !== cycleStart) {
            curr = edges[curr];
            cycleSize++;
        }
        
        // 标记环中的节点并设置答案
        curr = cycleStart;
        do {
            inCycle[curr] = true;
            answer[curr] = cycleSize;
            visited[curr] = true;
            curr = edges[curr];
        } while (curr !== cycleStart);
    }
    
    // 计算环外节点的答案
    function dfs(node) {
        if (answer[node] !== -1) return answer[node];
        answer[node] = dfs(edges[node]) + 1;
        return answer[node];
    }
    
    for (let i = 0; i < n; i++) {
        if (answer[i]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度
时间复杂度	O(n)
空间复杂度	O(n)

时间复杂度分析：虽然代码中有嵌套循环，但每个节点最多被访问常数次。快慢指针找环的时间复杂度是O(n)，DFS计算答案时每个节点也只被访问一次，因此总体时间复杂度为O(n)。

空间复杂度分析：需要额外的数组存储答案、访问状态等信息，以及递归调用栈的空间，最坏情况下为O(n)。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析