P3367 【模板】并查集

题目背景

本题数据范围已经更新到 ，。

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 ,表示共有 个元素和 个操作。

接下来 行，每行包含三个整数 。

当 时，将 与 所在的集合合并。

当 时，输出 与 是否在同一集合内，是的输出Y ；否则输出 N 。

输出格式

对于每一个 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例 #1

输入 #1

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1

N
Y
N
Y

说明/提示

对于 的数据，，。

对于 的数据，，。

对于 的数据，，。

对于 的数据，，，，。

题解

代码

#include<stdio.h>
int arr[200005],high[200005];
int n,t,z,x,y;

int find(int x){
    return x==arr[x] ? x: find(arr[x]);
}
void con(int x,int y){
    x=find(x);
    y=find(y);
    if (high[x]==high[y]){
        arr[x]=arr[y];
        high[y]+=1;

    }
    else{
        if (high[x]>high[y]) arr[y]=arr[x];
        else      arr[x]=arr[y];
    }
}
int main(){
    scanf("%d %d",&n,&t) ;
    for (int i=1 ;i<n+1;i++){
        arr[i]=i;
        high[i]=0;
    }
    while (t--)
    {
        scanf("%d %d %d",&z,&x,&y);
        if (z==1){
            con(x,y);
        }
        else{
            if (find(x)!=find(y)){
                printf("N\n");
            }
            else{printf("Y\n");}
        }
    }
    return 0;
}

解析

这是并查集模板题，主要是合并和查询，一开始没有优化，超时了，后面加了合并优化通过了