代码随想录算法训练day62---图论系列6《并查集2》

代码随想录算法训练

—day62

文章目录

代码随想录算法训练
前言
一、108.冗余连接
二、109. 冗余连接II
总结

前言

今天是算法营的第62天，希望自己能够坚持下来！
今天继续并查集系列！今日任务：
● 108.冗余连接
● 109.冗余连接II

一、108.冗余连接

卡码网题目链接
文章讲解

思路：
无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树。
如果有多个答案，则返回二维数组中最后出现的边。
那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合。
如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。
在这里插入图片描述

代码如下：

#include<iostream>
#include<vector>
using namespace std;int n;
vector<int> father = vector<int>(1001, 0);void init() {for (int i = 1; i <= n; i++) {father[i] = i;}
}int find(int u) {return u == father[u]? u : father[u] = find(father[u]);
}bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}void join(int u, int v) {u = find(u);v = find(v);if (u == v) return;father[v] = u;
}//遍历每一条边，把每一条边加入集合，当s,t同根的时候，说明发生了闭环，此时的s,t就是要去掉边
int main() {int s, t;cin >> n;init();for (int i = 1; i <= n; i++) {cin >> s >> t;if (isSame(s, t)) {cout << s << " " << t << endl;return 0;} else {join(s, t);}}
}

二、109. 冗余连接II

卡码网题目链接
文章讲解

思路：
与 108.冗余连接类似，但本题是一个有向图，有向图相对要复杂一些。

如果是有向树的话，只有根节点入度为0，其他节点入度都为1
所以情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了。
在这里插入图片描述
但入度为2 还有一种情况，情况二，只能删特定的一条边，如图：
综上，如果发现入度为2的节点，我们需要判断删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。

情况三：如果没有入度为2的点，说明图中有环了（注意是有向环）。
在这里插入图片描述
对于情况三，删掉构成环的边就可以了。

#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> father = vector<int>(1001, 0);void init() {for (int i = 1; i <= n; i++) {father[i] = i;}
}int find(int u) {return u == father[u]? u : father[u] = find(father[u]);
}bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}void join(int u, int v) {u = find(u);v = find(v);if (u == v) return;father[v] = u;
}void getRemoveEdge(const vector<vector<int>>& edges) {init();for (int i = 0; i < n; i++) {if (isSame(edges[i][0], edges[i][1])) { //构成环了，这条就是要删的边cout << edges[i][0] << " " << edges[i][1] << endl;} else {join(edges[i][0], edges[i][1]);}}
}bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {init();for (int i = 0; i < n; i++) {if (i == deleteEdge) continue; //要删掉的边不添加到集合中if (isSame(edges[i][0], edges[i][1])) { //构成环了，说明不是树return false;}join(edges[i][0], edges[i][1]);}return true;
}int main() {int s, t;vector<vector<int>> edges; //用来存放每条边cin >> n;vector<int> inDegree(n + 1, 0); //记录节点入度for (int i = 0 ;i < n; i++) {cin >> s >> t; //s->tinDegree[t]++; //t的入度+1edges.push_back({s,t}); //存放每条边}vector<int> vec; //存放入度为2的边//遍历每行，判断指向的节点是否入度为2，后序遍历，因为要优先删除最后出现的边for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) vec.push_back(i);}//情况一、情况二if (vec.size() > 0) {//放在vec里的边已经按照倒叙放了，所以这里优先删除vec[0]这条边if (isTreeAfterRemoveEdge(edges, vec[0])) {//如果删除这条边之后，是树，则这条边是答案，vec[0]是边的下标cout << edges[vec[0]][0] << " " << edges[vec[0]][1] << endl;} else {cout << edges[vec[1]][0] << " " << edges[vec[1]][1] << endl;}return 0;}//情况三，没有入度为2的节点，说明有环,找到构成环的边返回就可以了getRemoveEdge(edges);return 0;
}