107. 寻找存在的路径
这是道简单的并查集题目,设计插入,查找函数,比较基础
1、条件准备
father数组存每个结点的祖宗结点是谁
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
#define endl '\n'
int father[105];
int n,m;
2、主函数
首先初始化,每个结点的祖宗结点是本身。
然后插入边,更新father数组,通过join函数来实现
然后输入待查找的两结点,判断一下它们的祖宗结点是否一样
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
rep(i,1,n)
father[i]=i;
rep(i,1,m)
{
int a,b;cin>>a>>b;
join(a,b);
}
int be,en;cin>>be>>en;
if(find(be)==find(en))cout<<"1";
else cout<<"0";
return 0;
}
3、find函数
如果祖宗结点是本身,则已经找到祖宗结点,返回。
否则找该结点的父节点的祖宗结点,并进行路径压缩。
int find(int u)
{
return u==father[u]?u:father[u]=find(father[u]);
}
4、join函数
找出这两个结点的祖宗结点。如果一样则什么都不做。
否则更新其中一个的祖宗结点为另一个。
void join(int u,int v)
{
u=find(u);
v=find(v);
if(u==v)return ;
father[u]=v;
}
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[105];
int n,m;
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>>m;
rep(i,1,n)
father[i]=i;
rep(i,1,m)
{
int a,b;cin>>a>>b;
join(a,b);
}
int be,en;cin>>be>>en;
if(find(be)==find(en))cout<<"1";
else cout<<"0";
return 0;
}