详细讲解如何求解「内向基环森林」问题

站长

2024年03月11日 16:44 · 阅读数 3

题目描述

这是 LeetCode 上的 2876. 有向图访问计数 ，难度为困难。

Tag : 「基环森林」、「内向基环树」、「拓扑排序」、「图」、「BFS」

现有一个有向图，其中包含 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.lengthn = edges.lengthn=edges.length
2<=n<=1052 <= n <= 10^52<=n<=105
0<=edges[i]<=n−10 <= edges[i] <= n - 10<=edges[i]<=n−1
edges[i]!=iedges[i] != iedges[i]!=i

内向基环森林 + 拓扑排序

根据题意，共 n 个点，n 条边，利用 edges，将 i 向 edges[i] 连有向边，可知每个点有唯一的出边，因此这是一张可能包含多棵「内向基环树」的「基环森林」。

基环树是指其具有 nnn 个点 nnn 条边的联通块，而「内向」是指树中任意节点有且只有一条出边，对应的「外向」是指树中任意节点有且只有一条入边。

例如，左图内向，右图外向：

详细讲解如何求解「内向基环森林」问题

显然，可根据当前节点是否在“环内”进行分情况讨论：

对于「环内」节点来说，其答案为环节点个数；
对于「环外」节点来说，直观感受应该是由环上节点转移而来。但由于本题给定的是「内向基环树」，因此我们需要对原图进行“反向”，然后从环内节点开始，进行 BFS ，从而更新其余非环节点答案。

具体的，我们使用如下思路进行求解：

创建大小为 n 的数组 in，进行入度统计；
根据入度进行「拓扑排序」，剩余满足 in[i]≠0in[i] \neq 0in[i]=0 的点，为「环内」的点。我们可处理出每个点所在环的大小，环的大小为这些点的答案。处理过程中收集这些「环内」的点（将来要从它们出发，更新其他「环外」节点）
对原图进行“反向”，从收集好的「环内」点进行出发，运用 BFS 得出剩余点答案。

Java 代码：

class Solution {
    int N = 200010, M = N, idx = 0;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    public int[] countVisitedNodes(List<Integer> edges) {
        int n = edges.size();
        int[] in = new int[n], ans = new int[n];
        for (int x : edges) in[x]++;
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) d.addLast(i);
        }
        while (!d.isEmpty()) {
            int t = edges.get(d.pollFirst());
            if (--in[t] == 0) d.addLast(t);
        }
        // 处理环上的
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) continue;
            List<Integer> list = new ArrayList<>();
            list.add(i);
            int j = edges.get(i), val = 1;
            while (j != i) {
                list.add(j);
                j = edges.get(j);
                val++;
            }
            for (int x : list) {
                set.add(x);
                in[x] = 0;
                ans[x] = val;
            }
        }
        // 建立反向图, 处理非环上的, 从环内点出发进行往外更新
        Arrays.fill(he, -1);
        for (int i = 0; i < n; i++) add(edges.get(i), i);
        for (int u : set) {
            int val = ans[u];
            Deque<Integer> de = new ArrayDeque<>();
            de.addLast(u);
            while (!de.isEmpty()) {
                int sz = de.size();
                while (sz-- > 0) {
                    int t = de.pollFirst();
                    ans[t] = val;
                    for (int i = he[t]; i != -1; i = ne[i]) {
                        int j = e[i];
                        if (ans[j] != 0) continue;
                        de.addLast(j);
                    }
                }
                val++;
            }
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int he[200010], e[200010], ne[200010], idx;
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    vector<int> countVisitedNodes(vector<int>& edges) {
        int n = edges.size();
        vector<int> in(n, 0), ans(n, 0);
        for (int x : edges) in[x]++;
        queue<int> d;
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) d.push(i);
        }
        while (!d.empty()) {
            int t = edges[d.front()];
            d.pop();
            if (--in[t] == 0) d.push(t);
        }
        set<int> s;
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) continue;
            vector<int> list;
            list.push_back(i);
            int j = edges[i], val = 1;
            while (j != i) {
                list.push_back(j);
                j = edges[j];
                val++;
            }
            for (int x : list) {
                s.insert(x);
                in[x] = 0;
                ans[x] = val;
            }
        }
        memset(he, -1, sizeof(he));
        for (int i = 0; i < n; i++) add(edges[i], i);
        for (int u : s) {
            int val = ans[u];
            queue<int> de;
            de.push(u);
            while (!de.empty()) {
                int sz = de.size();
                while (sz-- > 0) {
                    int t = de.front();
                    de.pop();
                    ans[t] = val;
                    for (int i = he[t]; i != -1; i = ne[i]) {
                        int j = e[i];
                        if (ans[j] != 0) continue;
                        de.push(j);
                    }
                }
                val++;
            }
        }
        return ans;
    }
};

时间复杂度：统计入度复杂度为 O(n)O(n)O(n)；拓扑排序复杂度为 O(n)O(n)O(n)；统计「环内」节点答案复杂度为 O(n)O(n)O(n)；统计「环外」答案复杂度为 O(n)O(n)O(n)。整体复杂度为 O(n)O(n)O(n)
空间复杂度：O(n)O(n)O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2876 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地 🎉🎉