题目：108.冗余连接
题目链接：
108. 冗余连接 (kamacoder.com)
代码：
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
vector<int>father;
int find(int u) {if (father[u] == u) {return u;}else {return father[u] = find(father[u]);}
}
void join(int u, int v) {u = find(u);v = find(v);if (u == v) return;father[v] = u;
}
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}
int main() {int n;cin >> n;father = vector<int>(n + 1);for (int i = 0; i <= n; i++) father[i] = i;for (int i = 0; i < n; i++) {int s, t;cin >> s >> t;if (isSame(s, t)) {cout << s << ' ' << t << endl;}else {join(s, t);}}}题目：109.冗余连接2
题目链接：
109. 冗余连接II (kamacoder.com)
代码：
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int n;
vector<int>father;
void init() {for (int i = 0; i <= n; i++) {father[i] = i;}
}
int find(int u) {if (u == father[u]) return u;else {return father[u] = find(father[u]);}
}
void join(int u, int v) {u = find(u);v = find(v);if (u == v) return;father[v] = u;
}
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}
bool isTree(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(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]);}}
}int main() {cin >> n;father = vector<int>(n + 1, 0);int s, t;vector<vector<int>>edges;vector<int>inDegree(n + 1, 0);//记录入度for (int i = 0; i < n; i++) {cin >> s >> t;edges.push_back({ s,t });inDegree[t]++;}vector<int>vec;//记录入度为2的边for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) {vec.push_back(i);}}if (vec.size() > 0) {//非环形if (isTree(edges, vec[0])) {cout << edges[vec[0]][0] << " " << edges[vec[0]][1];return 0;}else {cout << edges[vec[1]][0] << " " << edges[vec[1]][1];return 0;}}getRemoveEdge(edges);
}
