算法训练营day70

题目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;
}