冗余连接

108. 冗余连接 (kamacoder.com)

考虑使用并查集，逐次将s、t加入并查集中，当发现并查集中find(u)和find(v)相同时，输出u和v，表示删除的边即可。

#include <iostream>
#include <vector>
using namespace std;// 定义一个函数find，用于在并查集中找到元素u的根节点
int find(const vector<int>& check, int u) {if (u == check[u]) // 如果u是其自身的根，则返回ureturn u;else // 否则递归地查找u的根return find(check, check[u]);
}
// 定义一个函数join，用于合并两个集合
void join(vector<int>& check, int u, int v) {int n = find(check, u); // 找到u的根int m = find(check, v); // 找到v的根if (n == m) { // 如果两个根相同，说明加入边(u,v)会形成环cout << u << " " << v; // 输出这条边}check[m] = n; // 将v的根设置为u，实现集合的合并
}int main() {int N;cin >> N; // 输入节点数和边数vector<int> check(N + 1, 0); // 初始化并查集数组for (int i = 0; i <= N; i++) {check[i] = i; // 每个元素的根初始化为自己}int s, t;for (int i = 0; i < N; i++) {cin >> s >> t; // 输入一条边的两个节点join(check, s, t); // 将两个节点合并到同一个集合中}return 0;
}

时间复杂度为O(N)，空间复杂度为O(N)。

冗余连接II

109. 冗余连接II (kamacoder.com)

代码随想录 (programmercarl.com)

本题本质为：一个有向图是由一颗有向树和一条有向边组成，我们需要找到并删除那条边。

此外，“若有多条边可以删除，请输出标准输入中最后出现的一条边”，说明在两条边都可以删除的情况下，要删除顺序靠后的边。

对于一颗有向树而言，根节点入度为0，其余节点入度为1。

因此对应的删除有三种情况：

1.有一点入度为2，删除指向该节点的一条边

3的入度为2，删除1->3或2->3。

2.入度为2，但只能删除特定边。

此处3的入度为2，但删除4->3明显无济于事，因此在找到入度为2的点还需判断删除哪条边会使图成为有向树。

3没有入度为2的点，有环。

只需删掉构成环的靠后的边即可。

贴一下代码随想录的代码：

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> father (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]);
}
// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u);v = find(v);if (u == v) return ;father[v] = u;
}
// 判断 u 和 v是否找到同一个根
bool same(int u, int v) {u = find(u);v = find(v);return u == v;
}// 在有向图里找到删除的那条边，使其变成树
void getRemoveEdge(const vector<vector<int>>& edges) {init(); // 初始化并查集for (int i = 0; i < n; i++) { // 遍历所有的边if (same(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边cout << edges[i][0] << " " << edges[i][1];return;} 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 (same(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;inDegree[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;}// 处理情况三// 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了getRemoveEdge(edges);
}

算法的时间复杂度和空间复杂度为O(N)。