題目1：108. 冗余連接 (kamacoder.com)

#include<iostream>
#include<vector>using namespace std;int n;
vector<int> father(10001, 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;
}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;}else {join(s, t);}}return 0;
}

題目2：109. 冗余連接II (kamacoder.com)

三種情況：入度為2的時候，有兩種情況一種是刪哪個都行，另一種是刪掉之后可能出現環，這時候就要判斷刪除這個邊，是否成環了

如果沒有入度為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]);
}bool same(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 isTree(vector<vector<int>>& edge, int intnode) {init();for(int i = 0;i < n;i++) {if(i == intnode) continue;// 這里判斷去掉這個邊是否成環，這個實在入度為2的情況下if(same(edge[i][0], edge[i][1])) return false;else join(edge[i][0], edge[i][1]);}return true;
}void getremovedge(vector<vector<int>>& edge) {init();for(int i = 0;i < n;i++) {if(same(edge[i][0], edge[i][1])) {cout << edge[i][0] << "" << edge[i][1] << endl;return;}else join(edge[i][0], edge[i][1]);}
}int main() {cin >> n;vector<vector<int>> edge;vector<int> indgree(n + 1, 0);for(int i = 0;i < n;i++) {int s, t;cin >> s >> t;indgree[t]++;edge.push_back({s, t});}vector<int> vec;for(int i = n - 1;i >=0;i--) {if(indgree[edge[i][1]] == 2) {vec.push_back(i);}}if(vec.size() > 0) {if(isTree(edge, vec[0])) {cout << edge[vec[0]][0] << " " << edge[vec[0]][1] << endl;}else cout << edge[vec[1]][0] << " " << edge[vec[1]][1] << endl;return 0;}getremovedge(edge);return 0;
}