笔记：代码随想录算法训练营day62：108.冗余连接、109.冗余连接II

学习资料：代码随想录

108. 冗余连接

卡码网题目链接（ACM模式）

判断是否有环的依据为，利用并查集，isSame函数，判断当下这条边的两个节点入集前是否为同根，如果是的话，该边就是会构成环的那条边

#include <iostream>
#include <vector>
using namespace std;int n;
vector<int> father=vector<int>(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;
}int main(){int s,t;cin>>n;init();for(int i=0;i<n;i++){cin>>s>>t;if(isSame(s,t)) {cout<<s<<' '<<t<<endl;return 0;}else{join(s,t);}}
}

109. 冗余连接II

卡码网题目链接（ACM模式）

分三种情况：代码随想录

对于有两个入度的节点的情况，需要先倒序记录节点入度情况，找到入度为2的那个节点对应的两条边，判断应该删除哪条边。判断方法为，先看第一条（之前是倒序遍历，即看最后这条），用isSame函数判段是否为构成环的这条边，如果是，cout这条，如果不是cout另一条;

如果没有入度为2的节点，即情况3，直接用isSame函数判断就可以了

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> father=vector<int>(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 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 isTreeAfterDeleteEdge(const vector<vector<int>>& edges,int todelete){init();for(int i=0;i<n;i++){if(i==todelete){continue;}if(isSame(edges[i][0],edges[i][1])) return false;join(edges[i][0],edges[i][1]);}return true;
}void deletedEdge(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(){cin>>n;vector<vector<int>> edges;vector<int> inDegree(n+1,0);int s,t;for(int i=0;i<n;i++){cin>>s>>t;edges.push_back({s,t});inDegree[t]++;}vector<int> doubleDegree;for(int i=n-1;i>=0;i--){if(inDegree[edges[i][1]]==2){doubleDegree.push_back(i);}}if(doubleDegree.size()>0){if(isTreeAfterDeleteEdge(edges,doubleDegree[0])){cout<<edges[doubleDegree[0]][0]<<' '<<edges[doubleDegree[0]][1];}else{cout<<edges[doubleDegree[1]][0]<<' '<<edges[doubleDegree[1]][1];}return 0;}deletedEdge(edges);}

有几个小点：

1、既然 isTreeAfterRemoveEdge() 和 getRemoveEdge() 都是靠并查集判断是否成环，能不能只用 getRemoveEdge() 一个函数来处理所有情况？

不能！

getRemoveEdge() 只能处理「无入度为 2」的情况（即情况三），
如果你碰到的是「有一个点入度为 2」（即情况一、情况二），就必须要先判断删哪一条边，这一步 getRemoveEdge() 做不到。

2、对于find函数会改变并查集的结构，这并不改变每一个节点的根节点，所以虽然在join函数和isSame函数的使用中，find会使并查集结构改变，对判断没有影响

3、对于vector，赋值方法v[i] = x需要以前设置vector大小，赋值方法v.push_back(x)不需要提前设置vector大小