一个小问题,玄关
查看原帖
一个小问题,玄关
1099087
Future_Present楼主2024/8/8 22:16

我用pre[]pre[]数组维护前驱,find函数用于找前驱,那为什么checkcheck函数中不能用pre[a]==pre[b]pre[a]==pre[b]来判断aa,bb前驱是否一致呢

ACAC CodeCode

#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int n,m,pre[N],z,x,y;
int find(int x){
	if(pre[x]==x) return x;
	return pre[x]=find(pre[x]);
}
void Merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		pre[fx]=fy;
	return;
}
bool check(int a,int b){
	if(find(a)==find(b)) return true;
	return false;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		pre[i]=i;
	while(m--){
		cin>>z>>x>>y;
		if(z==1)
			Merge(x,y);
		else if(z==2)
		    cout<<(check(x,y)?"Y":"N")<<endl;
	}
    return 0;
}

2024/8/8 22:16
加载中...