网站的建设意义,盐城网站建设找哪家好,西安空调销售网站建设,深圳上市公司一览表时隔多年我终于又开始写博客了#xff0c;主要是已经放假了#xff0c;之前一直忙于考试和课设没有时间写博客#xff0c;学习笔记也因为买了iPad的缘故大部分都是手写的了。
假期想要把以前做过的项目都整理一下放在github和CSDN上。
也已经很久没有写算法题了#xff0…时隔多年我终于又开始写博客了主要是已经放假了之前一直忙于考试和课设没有时间写博客学习笔记也因为买了iPad的缘故大部分都是手写的了。
假期想要把以前做过的项目都整理一下放在github和CSDN上。
也已经很久没有写算法题了直接导致今天这道题虽然我看了题解但是自己还是写了好久。
题目描述
传送门
题目解析
题解有两种解法 第一种解法比较朴素就是按照关键边和伪关键边的定义。 关键边在所有MST中都会出现的边 关键边性质删除以后只能得到一个边权和更大的MST或者无法得到MST 伪关键边会出现在一些MST中但是不会出现在所有MST中的边
因此我们对每条边先判断是不是关键边如果不是再判断是否是伪关键边。 判断关键边的思路很清晰就是删去这条边再判断是否还能得到和之前边权和相同的MST。
但是判断伪关键边就有一些技巧了我们很难得到所有的最小生成树对于一条边我们如何判断这条边在不在MST中呢题解的做法是最先将这条边加入到MST中然后再对剩下的求解MST如果最后MST和之前的权值和相同则说明这条边在MST中。
我和题解不同的做法在于我认为是一点小优化
刚开始需要求一次MST求关键边的时候只枚举这个MST中的边其他的边不可能在伪关键边中使用kind数组记录每条边的属性在求完所有的关键边以后再求伪关键边如果某条边已经在一个MST中则直接加入伪关键边因为他不是关键边满足伪关键边的定义
第二种我直接没有看因为Tarjan算法我已经忘光了而且这道题好像还用到了kraskal算法的一个性质并不知道 在Kruskal 算法中对于任意的实数 w只要我们将给定的边按照权值从小到大进行排序那么当我们按照顺序处理完所有权值小于等于 w 的边之后对应的并查集的连通性是唯一确定的无论我们在排序时如何规定权值相同的边的顺序。 感觉太难了不想看了。
AC代码
class Solution {
public:static constexpr int MAXN 105;int father[MAXN];int kind[MAXN*MAXN];int m; //边数int value 0;int root(int x) {return x father[x] ? x : (father[x] root(father[x]));}void merge(int u, int v) {father[root(u)] root(v);}vectorint critical_edges;vectorint pseudo_critical_edges;/*** 求已经删去第del条边的图的最小生成树* 并差集的状态为father* cnt用来记录当前该最小生成树中有多少条边* ret用来记录当前最小生成树的权值和*/int kruskal(const int n, const vectorvectorint edges, int del, int cnt, int ret) {for (int i 0; i m; i) {if (i del) {//如果是已经删除的边则跳过continue;}int u edges[i][0];int v edges[i][1];if (root(u) ! root(v)) {merge(u, v);ret edges[i][2];cnt;if (kind[i] -1 del -1)kind[i] 0; //表示该边是某个最小生成树的一条边}}if (cnt n-1) {//说明形成了最小生成树return ret;} else {//说明原本不是一个连通分量return value 122;}}static bool compare(const vectorint a, const vectorint b) {return a[2] b[2];}vectorvectorint findCriticalAndPseudoCriticalEdges(int n, vectorvectorint edges) {memset(kind, -1, sizeof(kind));m edges.size();for (int i 0; i m; i) {edges[i].push_back(i);}sort(edges.begin(), edges.end(), compare);for (int i 0; i n; i) {//并查集的初始化father[i] i;}value kruskal(n, edges, -1, 0, 0);//寻找关键边for (int i 0; i m; i) {if (kind[i] -1) {//不是生成树中的边continue;}for (int i 0; i n; i) {//并查集的初始化father[i] i;}int v kruskal(n, edges, i, 0, 0);if (v value) {//说明是关键边kind[i] 1;critical_edges.push_back(edges[i][3]);}}//寻找伪关键边for (int i 0; i m; i) {if (kind[i] 1) continue; //关键边不可能是伪关键边if (kind[i] 0) {//如果在某个生成树中还不是关键边则一定是伪关键边pseudo_critical_edges.push_back(edges[i][3]);continue;}//对于普通边首先将其加入到生成树中然后再判断for (int i 0; i n; i) {//并查集的初始化father[i] i;}merge(edges[i][0], edges[i][1]);int v kruskal(n, edges, -1, 1, edges[i][2]);if (v value) {//说明加入这条边以后仍然能够得到最小生成树是伪关键边pseudo_critical_edges.push_back(edges[i][3]);}}return {critical_edges, pseudo_critical_edges};}
};官方题解代码
// 并查集模板
class UnionFind {
public:vectorint parent;vectorint size;int n;// 当前连通分量数目int setCount;public:UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {iota(parent.begin(), parent.end(), 0);}int findset(int x) {return parent[x] x ? x : parent[x] findset(parent[x]);}bool unite(int x, int y) {x findset(x);y findset(y);if (x y) {return false;}if (size[x] size[y]) {swap(x, y);}parent[y] x;size[x] size[y];--setCount;return true;}bool connected(int x, int y) {x findset(x);y findset(y);return x y;}
};class Solution {
public:vectorvectorint findCriticalAndPseudoCriticalEdges(int n, vectorvectorint 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];});// 计算 valueUnionFind uf_std(n);int value 0;for (int i 0; i m; i) {if (uf_std.unite(edges[i][0], edges[i][1])) {value edges[i][2];}}vectorvectorint ans(2);for (int i 0; i m; i) {// 判断是否是关键边UnionFind uf(n);int v 0;for (int j 0; j m; j) {if (i ! j uf.unite(edges[j][0], edges[j][1])) {v edges[j][2];}}if (uf.setCount ! 1 || (uf.setCount 1 v value)) {ans[0].push_back(edges[i][3]);continue;}// 判断是否是伪关键边uf UnionFind(n);uf.unite(edges[i][0], edges[i][1]);v edges[i][2];for (int j 0; j m; j) {if (i ! j uf.unite(edges[j][0], edges[j][1])) {v edges[j][2];}}if (v value) {ans[1].push_back(edges[i][3]);}}return ans;}
};//作者LeetCode-Solution
//链接https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/solution/zhao-dao-zui-xiao-sheng-cheng-shu-li-de-gu57q/
//来源力扣LeetCode
//著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。仔细研究官方题解的代码感觉收益颇多
使用iota(begin, end, init)对数组进行初始化其中init为初始值需要能够和运算符结合使用功能完善的并差集模板我自己每次都是手写然后写地支离破碎使用lamda表达式进行函数定义
