LeetCode 1489. 找到最小生成树里的关键边和伪关键边（并查集+kruskal最小生成树）

Michael阿明

发布于 2021-02-19 06:55:01

99000

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录

- 1. 题目
- 2. 解题

1. 题目

给你一个 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) 数对都是互不相同的。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

图–最小生成树并查集参考

解题见注释

class dsu{  //并查集
    vector<int> f;
public:
    dsu(int n)
    {
        f.resize(n);
        for(int i = 0; i < n; ++i)
            f[i] = i;
    }
    void merge(int a, int b)
    {
        int fa = find(a), fb = find(b);
        if(fa != fb)
        {
            f[fa] = fb;
        }
    }
    int find(int a)
    {
        if(a == f[a]) return a;
        return f[a] = find(f[a]);
    }
    void reset()
    {
        for(int i = 0; i < f.size(); ++i)
            f[i] = i;
    }
};
class Solution {
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        vector<int> edgeId(edges.size());
        iota(edgeId.begin(), edgeId.end(), 0);
        sort(edgeId.begin(), edgeId.end(),[&](auto a, auto b){
            return edges[a][2] < edges[b][2];//距离小的优先
        });
        dsu u(n);
        vector<bool> vis(edges.size(), false);
        int mincost = kruskal(vis, u, edgeId, edges, n, 0);//最小生成树权值
        vector<vector<int>> ans(2);
        for(int i = 0; i < edges.size(); ++i)
        {
            vis[i] = true;//删除这条边
            u.reset();//重置并查集
            int cost = kruskal(vis, u, edgeId, edges, n, 0);
            if(cost > mincost)//删除边以后，cost 变大，或 无法生成树
            {
                ans[0].push_back(i);//关键边
                vis[i] = false;
                continue;
            }
            u.reset();//重置并查集
            u.merge(edges[i][0], edges[i][1]);//不是关键边，且提前把这条边加入树中
            cost = kruskal(vis, u, edgeId, edges, n, edges[i][2]);
            if(cost == mincost)// 权值和 不变，伪关键边
                ans[1].push_back(i);
            vis[i] = false;//恢复这条边
        }
        return ans;
    }
    int kruskal(vector<bool>& vis, dsu& u, vector<int>& edgeId, vector<vector<int>>& edges, int n, int mincost)
    {
        int edge_count = (mincost ? 1 : 0);//提前加入边了吗
        int a, b, id, cost;
        for(int i = 0; i < edgeId.size(); ++i)
        {
            id = edgeId[i];
            if(vis[id]) continue;//边删除了
            a = edges[id][0];
            b = edges[id][1];
            cost = edges[id][2];
            if(u.find(a) != u.find(b))
            {
                u.merge(a, b);
                mincost += cost;
                edge_count++;
            }
            if(edge_count == n-1)
                return mincost;
        }
        return INT_MAX;//无法构造生成树
    }
};