Loading... # 问题 [LeetCode #1489](https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/) 本题其实就是三个问题。求最小生成树、不含某条边的最小生成树（可能有也可能没有），一定含某条边的最小生成树。详细分析可见LeetCode上的题解。 # 解决 因为本题考查的是边，因此用针对边的Kruskal算法即可，这样都不用转换图的表示形式，直接用给定的边集即可。 Kruskal其实属于贪心算法。 Kruskal算法中加入新边时需要考查两个点是否已经被连接，根据网上资料，这个问题可用并查集高效解决。 最后，在代码实现上，我写了一个Kruskal类和一个DSU（Disjoint Set Union，并查集）类（带路径压缩）。借助二者即可完成Solution类。 之所以DSU类中写了两个findFather，是因为我一开始写的是非递归的版本（数据大时可防止爆栈），但是可能因为其中使用的Stack增加了时间复杂度，LeetCode上超时。之后改成了递归版本即可通过。整个速度稍慢，不知道是不是因为使用了很多STL模板而LeetCode没开O2优化的原因。 ```cpp class DSU // Disjoint Set Union { vector<int> fathers; public: DSU(const int n) { // initialize for (int i = 0; i < n; i++) fathers.push_back(i); } DSU() = default; void init(const int n) { if (fathers.size()) return; for (int i = 0; i < n; i++) fathers.push_back(i); } int findFather(const int x) { if (fathers[x] == x) return x; else { fathers[x] = findFather(fathers[x]); return fathers[x]; } } int findFather2(const int x) { int now = x, father = fathers[x]; stack<int> to_modify; while (now != father) { to_modify.push(now); now = father; father = fathers[father]; } while (!to_modify.empty()) { fathers[to_modify.top()] = father; to_modify.pop(); } return father; } bool unionTwo(const int x, const int y) { int x_father = findFather(x), y_father = findFather(y); if (x_father == y_father) return false; else { fathers[y_father] = fathers[x_father]; return true; } } }; class Kruskal { int n; vector<vector<int>>& edges; vector<int> tree; int exist_edge; int del_edge; int total; DSU dsu; public: Kruskal() = default; Kruskal(const int _n, vector<vector<int>>& _edges, const int _exist_edge, const int _del_edge): n(_n), edges(_edges), exist_edge(_exist_edge), del_edge(_del_edge), total(0) { dsu.init(n); if (exist_edge != -1) { tree.push_back(exist_edge); auto &e = edges[exist_edge]; total += e[2]; dsu.unionTwo(e[0], e[1]); } mst(); } int mst() { for (int i = 0; i < edges.size(); i++) { if (i != exist_edge && i != del_edge) { if (dsu.findFather(edges[i][0]) != dsu.findFather(edges[i][1])) { tree.push_back(i); dsu.unionTwo(edges[i][0], edges[i][1]); total += edges[i][2]; } } if (tree.size() == n - 1) return total; } total = -1; return -1; } int total_value() { return total; } }; class Solution { static bool cmp(vector<int>& x, vector<int>& y) { return x[2] < y[2]; } public: vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) { for (int i = 0; i < edges.size(); i++) { edges[i].push_back(i); // e[i] = {from, to, w, index} } sort(edges.begin(), edges.end(), cmp); vector< vector<int> > ans(2); int mst = Kruskal(n, edges, -1, -1).total_value(); for (int i = 0; i < edges.size(); i++) { auto& e = edges[i]; int mst_del_e = Kruskal(n, edges, -1, i).total_value(); if (mst_del_e == -1 || mst_del_e > mst) ans[0].push_back(e[3]); else { int mst_exist_e = Kruskal(n, edges, i, -1).total_value(); if (mst_exist_e == mst) ans[1].push_back(e[3]); } } return ans; } }; ``` -------- 参考资料： [最小生成树与并查集（leetcode684，685， 721）](https://blog.csdn.net/yinyu19950811/article/details/89461166) [算法学习笔记(1) : 并查集](https://zhuanlan.zhihu.com/p/93647900) Last modification：June 27th, 2020 at 03:26 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 Appreciate the author