题目

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

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

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

示例 1：

输入：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]]
解释：上图描述了给定图。
下图是所有的最小生成树。

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

示例 2 ：

输入：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) 数对都是互不相同的。

思路

并查集！

解法

class Solution {
public static List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        // 按权值排序
        Set<Edge> edgeSet = new TreeSet<>((e1, e2) -> {
            if (e1.weight != e2.weight) {
                return e1.weight - e2.weight;
            } else {
                return e1.edgeIndex - e2.edgeIndex;
            }
        });
        for (int i = 0; i < edges.length; i++) {
            Edge e = new Edge(edges[i][0], edges[i][1], edges[i][2], i);
            edgeSet.add(e);
        }
        UDFS udfs = new UDFS(n);
        int minTotalWeight = 0;
        // 存储一个生成树的边的解集
        Set<Integer> oneSolution = new HashSet<>();
        // 这里存储所有非关键边
        Set<Integer> pseudoEdgeIndexList = new HashSet<>();
        int nodeConnected = 1;
        // 先找出一个最小生成树
        for (Edge edge : edgeSet) {
            if (nodeConnected == n) {
                pseudoEdgeIndexList.add(edge.edgeIndex);
            }
            if (udfs.union(edge.from, edge.to)) {
                minTotalWeight += edge.weight;
                oneSolution.add(edge.edgeIndex);
                nodeConnected++;
            } else {
                pseudoEdgeIndexList.add(edge.edgeIndex);
            }
        }
        Set<Integer> pseudoEdgeResult = new HashSet<>();
        // 然后一条边一条边地删...
        for (int index1 : oneSolution) {
            udfs = new UDFS(n);
            int totalWeight = 0;
            // 除了待删除的一条边，把其他边连起来，算权值和，和构建并查集
            for (int index2 : oneSolution) {
                if (index2 == index1) {
                    continue;
                }
                int[] oneEdge = edges[index2];
                udfs.union(oneEdge[0], oneEdge[1]);
                totalWeight += oneEdge[2];
            }
            // 存储当前并查集状态
            int[] tmpParent = Arrays.copyOf(udfs.parent, udfs.parent.length);
            int[] tmpRank  = Arrays.copyOf(udfs.rank, udfs.rank.length);
            // 在剩下的边里找一条能构成最小生成树的边，如果找到了就说明待删除的边不是关键边
            for (Integer integer : pseudoEdgeIndexList) {
                udfs.parent = Arrays.copyOf(tmpParent, udfs.parent.length);
                udfs.rank = Arrays.copyOf(tmpRank, udfs.rank.length);
                int[] oneEdge = edges[integer];
                if (udfs.union(oneEdge[0], oneEdge[1])) {
                    if (minTotalWeight >= totalWeight + oneEdge[2]) {
                        pseudoEdgeResult.add(integer);
                        pseudoEdgeResult.add(index1);
                    }
                }
            }
        }
        pseudoEdgeResult.forEach(oneSolution::remove);
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>(oneSolution).stream().sorted().collect(Collectors.toList()));
        result.add(new ArrayList<>(pseudoEdgeResult).stream().sorted().collect(Collectors.toList()));
        return result;
    }

    private static class Edge {
        int weight;
        int from;
        int to;
        int edgeIndex;

        public Edge(int from, int to, int weight, int edgeIndex) {
            this.weight = weight;
            this.from = from;
            this.to = to;
            this.edgeIndex = edgeIndex;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Edge) {
                return ((Edge) obj).weight == this.weight && ((Edge) obj).from == this.from
                        && ((Edge) obj).to == this.to && ((Edge) obj).edgeIndex == this.edgeIndex;
            }
            return false;
        }
    }

    private static class UDFS {
        private int[] parent;
        private int[] rank;

        public UDFS(int n) {
            this.parent = new int[n];
            this.rank = new int[n];
            for (int i = 0; i < n; i++) {
                rank[i] = 1;
                parent[i] = i;
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            } else {
                int root = find(parent[i]);
                parent[i] = root;
                return root;
            }
        }

        public boolean union(int from, int to) {
            int rootx = find(from);
            int rooty = find(to);
            if (rooty == rootx) {
                return false;
            }
            if (rank[rootx] <= rank[rooty]) {
                parent[rootx] = rooty;
            } else {
                parent[rooty] = rootx;
            }
            if (rank[rootx] == rank[rooty]) {
                rank[rootx]++;
            }
            return true;
        }
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现