Studying-代码随想录训练营day56| 108.冗余连接、109.冗余连接II

第56天，图论06，并查集题目类型冗余连接(ง •_•)ง💪，编程语言：C++

目录

108.冗余连接

109.冗余连接II

总结

---

108.冗余连接

文档讲解：手撕冗余连接

题目：108. 冗余连接 (kamacoder.com)

学习：本题也可以用并查集的方法进行求解。原因在于要使得删除一条边后，图变为一棵树，也即只有一个根节点。

只有一个根节点也就意味着大家都在一个集合之中。因此我们可以采取从前向后遍历的顺序，遍历每一条边，边的两个节点如果不再同一个集合，就加入集合。

如果在同一个集合，那就说明这条边的两个节点，已经连通了，加入这条边一定会出现环，则需要将这条边删除。（并且事实上在我们发现这条边的时候，就已经是我们找到的答案中的最后出现的边了，因为我们是从前往后遍历的，遍历到这条边，就已经是必须要删除的状态了）

代码：先写出并查集模板，然后进行求解

#include <iostream>
#include <vector>
using namespace std;//并查集模版
int n;
vector<int> father(n + 1, 0); //节点从1开始，因此我们定义一个n+1大小的数组void init() { //初始化father数组for(int i = 0; i <= n; i++) {father[i] = i;}
}int find(int u) { //寻根函数// return u == father ? u : father[u] = find(father[u]); //简化写法if(u == father[u]) return u; //自身就是根return 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;
}int main() {cin >> n;init(); //初始化数组int s, t;for (int i = 0; i < n; i++) { //进行并查集合并cin >> s >> t;if (isSame(s, t)) {cout << s << " " << t << endl;return 0;} else {join(s, t);}}return 0;
}

---

109.冗余连接II

文档讲解：手撕冗余连接II

题目：109. 冗余连接II (kamacoder.com)

学习：本题是将无向图转变为有向图，相对的会复杂一些。但我们需要明确，本题中的有向图，指的是一颗有向树+一条有向边组成的。同时有向树的特点在于，只有根节点的入度为0，其他节点入度都为1。

基于此我们可以考虑两种情况：第一种情况有一个节点的入度为2；第二种情况存在环（即没有入度为0的根节点）

第一种情况又可以分为两种情形：

1.如果我们找到入度为2的点，那么删除一条指向该节点的边就行。以下图为例，删1 -> 3 或者 2 -> 3都可以，选择删除顺序靠后便可。

2.入度为2也有另一种情况，只能删除特定的一条边。以下图为例，只能删除边1->3，另一条边是不可以删除的，会丢失一个点。

第二种情况没有入度为2的点，而是存在环。以下图为例，删除构成环的边，使得到一个入度为0的根节点即可。

分析好了以上三种情形之后，我们就可以针对性的进行代码的书写。

针对第一种情况：我们可以统计每个节点的度，找寻是否有节点度为2的节点。

    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;inDegree[t]++;edges.push_back({s, t});}

如果有的话，一定是删除指向入度为2的节点的两条边其中的一条，如果删了一条，判断这个图是一个树，则这条边就是答案（同时我们还要保证是从前往后遍历的，以便于我们删除最后一条边） 

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])) {cout << edges[vec[0]][0] << " " << edges[vec[0]][1];} else {cout << edges[vec[1]][0] << " " << edges[vec[1]][1];}return 0;
}

而对于第二种情况也就是出现环的情况，则我们按照上一题的办法，找到成环的边即可。

// 在有向图里找到删除的那条边，使其变成树 
void getRemoveEdge(const vector<vector<int>>& edges)

接下来我们就是要实现 isTreeAfterRemoveEdge()和getRemoveEdge()，这两个函数了。

第一个函数用于判断删除一个边之后是不是有向树，方法是通过将所有边的两端节点加入并查集，遇到要删除的边则跳过，只有删除了正确的边，才能够将所有节点都加入并查集。否则会出现丢失点，并且另外的点成环的情况。

第二个函数则是确定了有环，则我们只需要将所有边的两端节点加入并查集，并且从前往后，直到遇到第一个使得并查集出现重复的边，则说明这条边是要删除的边。

由此可以看出这两个函数的实现，其实都可以是在上一题基础上进行实现的。

代码：在并查集的基础上，加入两函数

#include <iostream>
#include <vector>
using namespace std;//并查集模版
int n;
vector<int> father(1001, 0); //节点从1开始，因此我们定义一个n+1大小的数组void init() { //初始化father数组for(int i = 0; i <= n; i++) {father[i] = i;}
}int find(int u) { //寻根函数// return u == father ? u : father[u] = find(father[u]); //简化写法if(u == father[u]) return u; //自身就是根return 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;
}// 删一条边之后判断是不是树
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;
}// 在有向图里找到删除的那条边，使其变成树
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];return;} else {join(edges[i][0], edges[i][1]);}}
}int main() {cin >> n;int s, t;vector<vector<int>> edges; //保存边vector<int> inDegree(n + 1, 0); // 记录节点入度for (int i = 0; i < n; i++) {cin >> s >> t;inDegree[t]++; //t是入度edges.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])) { //判断当前边删除可不可以，如果不可以，则一定时删除另一条边cout << edges[vec[0]][0] << " " << edges[vec[0]][1];} else {cout << edges[vec[1]][0] << " " << edges[vec[1]][1];}return 0;}// 第二种情况getRemoveEdge(edges);return 0;
}

---

总结

今天的两道题，是对并查集的巩固考察。第二道题增加了对有向图的分析，但实际上还是使用了并查集具备的查找两个元素是否在一个集合，查找成环的能力。需要多加练习！！！