$$\huge\color{grey}{连通图——}\text{1道并查集模板}$$
题目大意
给定一个无向图和它的所有条边,请问这个图的所有节点是否两两连通?
算法思路
算法一:暴力搜索
直接套模板再修改。
算法二:并查集
这道题目非常适合使用并查集。
时空复杂度预估
算法一:暴力搜索
注意:这个算法有多种写法,以下只是最优的一种!
需要借助布尔型的邻接矩阵,时空复杂度均为$O(n^2)$。
算法二:并查集
不路径压缩、不优化
时间复杂度最坏$O(n^2)$(计算中途退化成链条)。空间复杂度恒定为$O(n)$左右。
不路径压缩、小优化
时间复杂度最坏$O(nlog_2{n})$(放置上一种情况的出现)。空间复杂度还是$O(n)$。
路径压缩
时间复杂度最坏$O(n)$,因为常数比对数函数还增长慢得多,所以就忽略不计了。空间复杂度仍为$O(n)$。
正确代码
算法一:暴力搜索
注意:写暴力最重要的是写对、易懂。
这里强烈推荐@浅默淡殇大佬写的dfs
:
点击跳转查看。
算法二:并查集
注意:这里的代码是路径压缩过的代码。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;//较高精度的浮点数
typedef pair<int,int> PII;
typedef pair<string,int> PSI;
const int N=1009;
const int M=5009;
int n,m;//如题
int p[N],cnt[N];
//p[i]表示i的最老祖先
//cnt[i]表示以i为根的子树的大小
int root (int x)
{
return p[x]==x?p[x]:p[x]=root(p[x]);
//路径压缩模板
}
int main ()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
while(cin>>n>>m)
{//不停输入
for (int i=1;i<=n;++i)
p[i]=i,cnt[i]=1;
//初始化i的最老祖先为自己、初始化以i为根的子树大小为1
for (int i=1;i<=m;++i)
{//处理每一个边
int x,y;
cin>>x>>y;
int rx=root(x),ry=root(y);//取出两端节点的最老直系祖先
if (rx!=ry)//如果不在同一个并查集块内
p[rx]=ry,cnt[ry]+=cnt[rx];//合并,挑一个当爹,另一个当儿子
}
puts(cnt[root(1)]==n?"YES":"NO");//让1当根判断
}
return 0;
}