自学按秩合并,尝试直接加路径压缩,1AC 9MLE 救命
查看原帖
自学按秩合并,尝试直接加路径压缩,1AC 9MLE 救命
318708
Cannot_without_you楼主2022/7/19 22:36
#include<cstdio>
#include<iostream>
using namespace std;
const int N=5e3+1;
int dep[N],f[N];
int fnd(int x){
	return f[x]==x?x:f[x]=fnd(f[x]);
}
inline void mer(int x,int y)
{
	int fx=fnd(x),fy=fnd(y);
	if(dep[fx]>dep[fy])
	f[fy]=fx;
	if(dep[fx]<dep[fy])
	f[fx]=fy;
	if(dep[fx]=dep[fy])
	f[fy]=fx,dep[fx]++;
}
inline bool bol(int x,int y)
{
	int fx=fnd(x),fy=fnd(y);
	if(fx!=fy)return false;
	return true;
}
int main()
{
	int n,m,q;
	register int i,j,x,y;
	scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<=n;i++)
	f[i]=i,dep[i]=1;
	for(i=1;i<=m;i++)
	scanf("%d%d",&x,&y),mer(x,y);
	for(i=1;i<=q;i++){
		scanf("%d%d",&x,&y);
		if(bol(x,y))
		printf("Yes\n");
		else
		printf("No\n");
	}
	return 0;
}
2022/7/19 22:36
加载中...