并查集模板——P3367

· · 个人记录

题目传送门

题目描述

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

输入格式

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

接下来 MM 行，每行包含三个整数 Zi,Xi,Yi,Zi。

当 Zi=1时，将 Xi与 Yi所在的集合合并。

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

输出格式

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

输入输出样例

输入

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

输出

N
Y
N
Y

说明/提示

对于 30% 的数据，N≤10，M≤20 。

对于 70% 的数据，N≤100，M≤10^3。

对于 100% 的数据，1≤N≤10^4，1≤M≤2×10 ^5。

思路

首先这是一道并查集的模板题，我们要了解并查集

补充知识

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受;即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。

基本函数（并查集{合并}{查找}{集合}）

寻找根节点

int findFather(int x){
    if(x==father[x])return x;
    int f=findFather(father[x]);
    father[x]=f;
    return f; 
}

合并两个并查集

void Union(int a,int b){
    int fA=findFather(a);
    int fB=findFather(b);
    if(fA!=fB)father[fA]=fB;
}

代码

#include<bits/stdc++.h>//3367
using namespace std;
int father[10001];
int findFather(int x){
    if(x==father[x])return x;
    int f=findFather(father[x]);
    father[x]=f;
    return f; 
}
void Union(int a,int b){
    int fA=findFather(a);
    int fB=findFather(b);
    if(fA!=fB)father[fA]=fB;
}
int main(){
    int n,m;
    cin>>n>>m;
    int a,b,c;
    for(int i=1;i<=n;i++){
        father[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        if(a==1){
            Union(b,c);
        }
        else{
            if(findFather(b)==findFather(c)){
                cout<<"Y"<<endl;
            }
            else{
                cout<<"N"<<endl;
            }
        }
    }
    return 0;
}