108. 冗余连接
继续使用查并集的方法,如果两个元素是在一个集合,那么我们就输出,反之加入集合。
#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){
if(father[u]==u) return u;
else return father[u]= find(father[u]);
}
bool compare(int s,int t){
s=find(s);
t=find(t);
return s==t;
}
void join(int s,int t){
s=find(s);
t=find(t);
if(s==t) return;
else father[s]=t;
}
int main(){
cin>>N;
int i,j;
init();
while(N--){
cin>>i>>j;
if(compare(i,j))
{
cout<<i<<" "<<j<<endl;
return 0;
}
else join(i,j);
}
}
109. 冗余连接II
我们要解决本题要实现两个最为关键的函数:
isTreeAfterRemoveEdge()
判断删一个边之后是不是有向树getRemoveEdge()
确定图中一定有了有向环,那么要找到需要删除的那条边
isTreeAfterRemoveEdge()
判断删一个边之后是不是有向树: 将所有边的两端节点分别加入并查集,遇到要删除的边则跳过,如果遇到即将加入并查集的边的两端节点本来就在并查集了,说明构成了环。如果顺利将所有边的两端节点(除了要删除的边)加入了并查集,则说明删除该条边还是一个有向树。
getRemoveEdge()
确定图中一定有了有向环,那么要找到需要删除的那条边: 将所有边的两端节点分别加入并查集,如果遇到即将加入并查集的边的两端节点 本来就在并查集了,说明构成了环。
#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){
if(u==father[u]) return u;
else return father[u]=find(father[u]);
}
bool compare(int s,int t){
s=find(s);
t=find(t);
return s==t;
}
void join(int s,int t){
s=find(s);
t=find(t);
if(s==t) return;
father[s]=t;
}
bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {
init(); // 初始化并查集
for (int i = 0; i < N; i++) {
if (i == deleteEdge) continue;
if (compare(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 (compare(edges[i][0], edges[i][1])) { // 构成有向环了,就是要删除的边
cout << edges[i][0] << " " << edges[i][1];
return;
} else {
join(edges[i][0], edges[i][1]);
}
}
}
int main(){
int s,t;
vector<vector<int>> edges;
cin>>N;
vector<int> isDegree(N+1);//记录节点入度数
for(int i=0;i<N;i++){
cin>>s>>t;
isDegree[t]++;
edges.push_back({s,t});
}
//记录度为二的边
//找入度为2的节点所对应的边,注意要倒序,因为优先删除最后出现的一条边
vector<int> vec;
for(int i=N-1;i>=0;i--){
if(isDegree[edges[i][1]]==2) vec.push_back(i);
}
if(vec.size()>0){
if(isTreeAfterRemoveEdge(edges, vec[0])){
cout << edges[vec[0]][0] << " " << edges[vec[0]][1];
}
else{
cout << edges[vec[1]][0] << " " << edges[vec[1]][1];
}
return 0;
}
getRemoveEdge(edges);
}
标签:vector,int,查集,节点,init,edges,第五十六,连接,冗余
From: https://blog.csdn.net/m0_69189584/article/details/140821781