题目描述

给你一个 n 个点的带权无向连通图,节点编号为 0 到 n-1 ,同时还有一个数组 edges ,其中 edges[i] = [from i, to i, weight i] 表示在 from i 和 to i 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集,它连接了所有节点且没有环,而且这些边的权值和最小。

请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边,会导致最小生成树的权值和增加,那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

请注意,你可以分别以任意顺序返回关键边的下标和伪关键边的下标。

 

示例 1:

ex1LeetCode.png

输入:n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
输出:[[0,1],[2,3,4,5]]
解释:上图描述了给定图。
下图是所有的最小生成树。

mstsLeetCode.png

注意到第 0 条边和第 1 条边出现在了所有最小生成树中,所以它们是关键边,我们将这两个下标作为输出的第一个列表。
边 2,3,4 和 5 是所有 MST 的剩余边,所以它们是伪关键边。我们将它们作为输出的第二个列表。

示例 2:

ex2LeetCode.png

输入:n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
输出:[[],[0,1,2,3]]
解释:可以观察到 4 条边都有相同的权值,任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。

提示:

  • 2 <= n <= 100
  • 1 <= edges.length <= min(200, n * (n - 1) / 2)
  • edges[i].length == 3
  • 0 <= fromi < toi < n
  • 1 <= weighti <= 1000
  • 所有 (fromi, toi) 数对都是互不相同的。

写在前面

要想写出这题,首先要懂得「最小生成树」和对应求解最小生成树的「Kruskal」算法。

思路及算法

先要读懂题目对「关键边」和「伪关键边」的定义:

  • 关键边:如果从最小生成树中删去某一条边,会导致最小生成树的权值和增加,那么这就是一条关键边。换种话说就是,如果假设原图中最小生成树的权值和为 value,那么去掉这条边后就会产生两种情况:

    • 要么整个图不再连通,即不存在最小生成树;
    • 要么整个图连通,总权值和为 v,且 v > value
  • 伪关键边:可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。也就是说,先把这条边加入最小生成树中。设最终得到的最小生成树权值为 v,如果 v = value,那么这条边就是伪关键边。

注意

需要注意的是,关键边也可能是一条伪关键边。所以,我们先对原图执行 Kruskal 算法,得到最小生成树的权值 value,然后再枚举每一条边,首先根据上面的方法判断其是否是关键边,如果不是关键边,再判断其是否是伪关键边。

代码

class Solution {
 
    class UnionFind {
        private int[] parent;
        private int count;
 
        public UnionFind(int N) {
            parent = new int[N];
            this.count = N;
            for (int i = 0; i < N; i++) {
                parent[i] = i;
            }
        }
    
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
    
        public int find(int p) {
            while (p != parent[p]) {
                p = find(parent[p]);
            }
            return parent[p];
        }
    
        public void union(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot == qRoot) {
                return;
            }
            parent[pRoot] = qRoot;
            count--;
        }

        public int getCount() {
            return this.count;
        }
    }
 
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        int m = edges.length, value = 0;

        int[][] newEdges = new int[m][4];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < 3; ++j) {
                newEdges[i][j] = edges[i][j];
            }
            newEdges[i][3] = i;
        }

        Arrays.sort(newEdges, (v1, v2) -> {
            return v1[2] - v2[2];
        });

        UnionFind uf = new UnionFind(n);
        for (int []v : newEdges) {
            if (!uf.connected(v[0], v[1])) {
                value += v[2];
                uf.union(v[0], v[1]);
            }
        }

        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < 2; ++i) res.add(new ArrayList<>());

        for (int i = 0; i < m; ++i) {
            UnionFind ud = new UnionFind(n);
            int v = 0;

            // 寻找关键边
            for (int j = 0; j < m; ++j) {
                if (j != i && !ud.connected(newEdges[j][0], newEdges[j][1])) {
                    v += newEdges[j][2];
                    ud.union(newEdges[j][0], newEdges[j][1]);
                }
            }

            if (ud.getCount() > 1 || (ud.getCount() == 1 && v > value)) {
                res.get(0).add(newEdges[i][3]);
                continue;
            }

            // 寻找伪关键边
            ud = new UnionFind(n);
            ud.union(newEdges[i][0], newEdges[i][1]);
            v = newEdges[i][2];
            for (int j = 0; j < m; ++j) {
                if (i != j && !ud.connected(newEdges[j][0], newEdges[j][1])) {
                    v += newEdges[j][2];
                    ud.union(newEdges[j][0], newEdges[j][1]);
                }
            }

            if (v == value) res.get(1).add(newEdges[i][3]);
        }

        return res;
    }
}

原题链接:https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/

Q.E.D.