day56 第十一章：图论part06

108.冗余连接

注意init初始化

改进：

其实只有一条边冗余，改为，如果两条边在同一个集合里，就输出，不然加入。

#include <iostream>
#include <vector>
using namespace std;int n = 1005;
vector<int> father(n,0);void init(){for (int i=0;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[u] = v;
}int main(){int N;cin >>N;init(); //1111int s,t,redun_s, redun_t;bool result;while(N--){cin>>s>>t;result = isSame(s,t);if (result){redun_s = s;redun_t = t;}join(s,t);}cout << redun_s <<" "<< redun_t << endl;return 0;
}

109.冗余连接II

不好做：

1.入度为2：看删哪条边可以形成树，而不是环（因为只有两种可能，一个树，一个环）

2.没有入度为2的点：有向环，删最后形成环的那条

#include <iostream>
#include <vector>
using namespace std;int n;
vector<int> father(1001, 0);void init() {for (int i = 0; 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;
}bool isTreeAfterRemoveVec(const vector<vector<int>>& edges, int v) {init();for (int i = 0; i < n; i++) {if (i == v) {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;}join(edges[i][0], edges[i][1]);}
}int main() {// int N;cin >> n;// init(); //1111// n = 3;// vector<vector<int>> grid;// grid = {//     {1,2},//     {1,3},//     {2,3}// };vector<vector<int>> edges;vector<int> degrees(n+1, 0);int s, t;for(int i=0;i<n;i++) {cin >> s >> t;// s = grid[i][0];// t = grid[i][1];edges.push_back({ s,t });degrees[t]++;}//计算入度vector<int> vec;for (int i = 0; i < n; i++) {//cout << degrees[edges[i][1]] << " ";if (degrees[edges[i][1]] == 2) {vec.push_back(i);}}//情况1：入度为2，看删哪个if (vec.size() > 1) {if (isTreeAfterRemoveVec(edges, vec[1])) {cout << edges[vec[1]][0] << " " << edges[vec[1]][1] << endl;}else {cout << edges[vec[0]][0] << " " << edges[vec[0]][1] << endl;}return 0;}//情况2：有向环getRemoveEdge(edges);return 0;
}