代码随想录：冗余连接|、||

 如果没接触过并查集，可以先做代码随想录：107、寻找存在的路径-CSDN博客

108. 冗余连接

1、条件准备

并查集find函数，join函数

 #include <bits/stdc++.h>#define rep(i, l, r) for (int i = l; i <= r; i++)using namespace std;#define endl '\n'int father[1005];
int n;int find(int u)
{return u==father[u]?u:father[u]=find(father[u]);
}void join(int u,int v)
{u=find(u);v=find(v);if(u==v)return ;father[u]=v;
}

2、主函数

还是初始化father数组，然后输入边

如果边的两端点已经出现了，则输出。

int main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;rep(i,1,n)father[i]=i;rep(i,1,n){int a,b;cin>>a>>b;if(find(a)!=find(b))join(a,b);else {cout<<a<<' '<<b;return 0;}}return 0;}

3、总结

完整代码如下

  #include <bits/stdc++.h>#define rep(i, l, r) for (int i = l; i <= r; i++)using namespace std;#define endl '\n'int father[1005];
int n;int find(int u)
{return u==father[u]?u:father[u]=find(father[u]);
}void join(int u,int v)
{u=find(u);v=find(v);if(u==v)return ;father[u]=v;
}int main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;rep(i,1,n)father[i]=i;rep(i,1,n){int a,b;cin>>a>>b;if(find(a)!=find(b))join(a,b);else {cout<<a<<' '<<b;return 0;}}return 0;}

109. 冗余连接II

分两种情况讨论，一种是有环的，一种是某点入度为2的

1、条件准备

father数组存每个结点的祖宗结点，edges存输入的边，n为结点数量

indegree数组为结点的入度

  #include <bits/stdc++.h>#define rep(i, l, r) for (int i = l; i <= r; i++)using namespace std;#define endl '\n'int father[1005];
pair<int,int> edges[1005];
int n;
int indegree[1005];int find(int u)
{return u==father[u]?u:father[u]=find(father[u]);
}void join(int u,int v)
{u=find(u);v=find(v);if(u==v)return ;father[u]=v;
}

2、主函数

先初始化，tag数组是用来处理入度为2的情况的。

输入边，存到edges数组里，更新入度。

遍历一遍，把入度为2的两条边加入tag里。

然后看看删除靠后的那条边能否使剩下的为一棵树，不能则输出前面的那条边。

如果是环的情况，调用removeedge函数实现。

int main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);vector<int>tag ;cin>>n;rep(i,1,n)father[i]=i;rep(i,1,n){int a,b;cin>>a>>b;edges[i]={a,b};++indegree[b];}rep(i,1,n)if(indegree[edges[i].second]==2)tag.push_back(i);if(tag.size()){if(iftree(tag[1]))cout<<edges[tag[1]].first<<' '<<edges[tag[1]].second;else cout<<edges[tag[0]].first<<' '<<edges[tag[0]].second;return 0;}removeedge();return 0;}

3、iftree函数

遍历一下所有边，如果删去入度为2的靠后的边没有使剩下的为一棵树，则返回0.

是否为一棵树看每一条边的两端是否已经在一棵树上。

bool iftree(int deleteEdge)
{rep(i,1,n){if(i==deleteEdge)continue;if(find(edges[i].first)==find(edges[i].second))return 0;join(edges[i].first,edges[i].second);}return 1;
}

4、removeedge函数

找到成环的那条边，即该边两端已经在树中了，输出。

void removeedge()
{rep(i,1,n){if(find(edges[i].first)==find(edges[i].second)){ cout<<edges[i].first<<' '<<edges[i].second;return ;}join(edges[i].first,edges[i].second);}
}

5、总结

这道题就较为复杂了，开始时属于较难的并查集了

完整代码如下

  #include <bits/stdc++.h>#define rep(i, l, r) for (int i = l; i <= r; i++)using namespace std;#define endl '\n'int father[1005];
pair<int,int> edges[1005];
int n;
int indegree[1005];int find(int u)
{return u==father[u]?u:father[u]=find(father[u]);
}void join(int u,int v)
{u=find(u);v=find(v);if(u==v)return ;father[u]=v;
}void removeedge()
{rep(i,1,n){if(find(edges[i].first)==find(edges[i].second)){ cout<<edges[i].first<<' '<<edges[i].second;return ;}join(edges[i].first,edges[i].second);}
}bool iftree(int deleteEdge)
{rep(i,1,n){if(i==deleteEdge)continue;if(find(edges[i].first)==find(edges[i].second))return 0;join(edges[i].first,edges[i].second);}return 1;
}int main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);vector<int>tag ;cin>>n;rep(i,1,n)father[i]=i;rep(i,1,n){int a,b;cin>>a>>b;edges[i]={a,b};++indegree[b];}rep(i,1,n)if(indegree[edges[i].second]==2)tag.push_back(i);if(tag.size()){if(iftree(tag[1]))cout<<edges[tag[1]].first<<' '<<edges[tag[1]].second;else cout<<edges[tag[0]].first<<' '<<edges[tag[0]].second;return 0;}removeedge();return 0;}