文章
27
粉丝
0
获赞
127
访问
7.1k
#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;
}
为啥...
登录后发布评论
暂无评论,来抢沙发