旺崽的博客

要么天赋异禀，要么天道酬勤

0%

LeetCode 1489 找到最小生成树里的关键边和伪关键边

发表于 分类于 Valine：

题目描述

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

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

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

示例 1：

在这里插入图片描述

1
2
3
4
5
6
输入：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 ：

在这里插入图片描述

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

这题的关键是找边，所以只能用最小生成树的 Kruskal 算法。
我们先给所有边编号，先求一遍最小生成树的权值和 $value$，然后依次遍历所有边 $i$，先算去掉边 $i$ 的最小生成树的权值和 $v$，若此时无法构造最小生成树或者 $v>value$，则这条边一定是关键边；再算伪关键边，我们加上这条边的权值，再算一次最小生成树的权值和 $v$，若 $v=value$，证明该边没有出现在所有的最小生成树中，一定是伪关键边，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Unionset {
public:
    vector<int> father;
    vector<int> sum;
    int cnt = 0;
public:
    void init(int n) {
        father.resize(n);
        for (int i = 0; i < n; i++) father[i] = i;
        sum.resize(n);
        cnt = n;
    }

    int findFather(int x) {
        return x == father[x] ? x : father[x] = findFather(father[x]);
    }

    bool Union(int x, int y) {
        x = findFather(x), y = findFather(y);
        if (x == y) return 0;
        if (sum[x] < sum[y]) swap(x, y);
        father[y] = x;
        sum[x] += sum[y];
        --cnt;
        return 1;
    }
};

class Solution {
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>> &edges) {
        int m = edges.size();
        for (int i = 0; i < m; i++) edges[i].push_back(i);
        sort(edges.begin(), edges.end(), [](const auto &u, const auto &v) { return u[2] < v[2]; });
        int value = 0;
        Unionset a = Unionset();
        a.init(n);
        for (auto i:edges) if (a.Union(i[0], i[1])) value += i[2];
        vector<vector<int>> ans(2);
        for (int i = 0; i < m; i++) {
            Unionset b = Unionset();
            b.init(n);
            int v = 0;
            for (int j = 0; j < m; j++) {
                if (i != j && b.Union(edges[j][0], edges[j][1])) v += edges[j][2];
            }
            if (b.cnt != 1 || (b.cnt == 1 && v > value)) {
                ans[0].emplace_back(edges[i][3]);
                continue;
            }
            Unionset c = Unionset();
            c.init(n);
            c.Union(edges[i][0], edges[i][1]);
            v = edges[i][2];
            for (int j = 0; j < m; j++) {
                if (i != j && c.Union(edges[j][0], edges[j][1])) v += edges[j][2];
            }
            if (v == value) ans[1].push_back(edges[i][3]);
        }
        return ans;
    }
};