文章

27

粉丝

0

获赞

127

访问

7.1k

头像
P1586 并查集 答疑提问:
jsd VIP
P1586
发布于2025年3月13日 15:36
阅读数 82

#include<bits/stdc++.h>
using namespace std;

//25

const int maxn = 10001;

int f[maxn];


int  find(int x){
	//压缩路径优化
	 int root = x;
	 while(f[root]>0){
	 	root = f[root];
	 } 
	 //找到根结点数组下标 
	//压缩路径
	while(x!=root){
		int t = f[x];
		f[x] = root;
		x = t;
	} 
	return root;
}
void u(int root1,int root2){
	
	//树高优化
	 //小树并大数
	 if(f[root1]<f[root2]){//越小树越高,
	  	f[root1]+=f[root2] ;
	 	f[root2] = root1;
	 	
	 } else{
	 	f[root2]+=f[root1];
	 	f[root1] = root2;
	 	
	 }
	 
	
} 
int main(){
	
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=n;i++){
		f[i] = -1;
	}
	for(int i = 0;i<m;i++){
		int x,y,z;
		cin>>z>>x>>y;
		if(z == 1){
			//合并
			int root1 = find(x);
			int root2 = find(y);
			u(root1,root2); 
		}else if(z==2){
			int root1 = find(x);
			int root2 = find(y);
			if(root1!=root2){
				printf("N\n");
			}else{
				printf("Y\n");
			}
		}
		

	}
		
	return 0;
} 

为啥...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发