题解：P3367 【模板】并查集

whx_mc · 2025-03-18 19:44:52 · 题解

题解：洛谷 P3367 【模板】并查集

题目描述

传送门

给定 n 个元素（编号为 1 至 n），需要处理 m 次操作：

• ‌操作1‌：合并元素 x 和 y 所在的集合
• ‌操作2‌：判断 x 和 y 是否属于同一集合

‌输入格式‌

• 第一行两个整数 n, m
• 接下来 m 行，每行三个整数 z, x, y（z=1 为合并，z=2 为查询）

‌输出格式‌

• 对每个查询操作，输出一行 Y 或 N

算法思路

并查集核心操作

1. ‌查询（Find）‌

   • 递归查找根节点，并进行路径压缩优化
   • 路径压缩：将路径上的所有节点直接指向根节点

2. ‌合并（Union）‌

   • 将两个集合的根节点连接

时间复杂度

• 单次操作平均复杂度：接近 O(1)
• 整体复杂度：O(m α(n))，其中 α(n) 为阿克曼函数的反函数

代码实现（不要抄啊）

#include<bits/stdc++.h>
int father[220006];
int find(int k){//寻找 
    if(father[k]==k)return k;
    return father[k]=find(father[k]);//边界 
} 
int main(){
    int n,m;
    std::cin>>n>>m;
    for(int i=1;i<=n;i++){
        father[i]=i;
    }
    for(int i=1;i<=m;i++){
        int z,x,y;
        std::cin>>z>>x>>y;
        if(z==1){   // 合并根节点 
            father[find(x)]=find(y);
        }
        else{
            if(find(x)==find(y)){ 
                std::cout<<"Y"<<"\n";
            }
            else{
                std::cout<<"N"<<"\n";
            }
        }
    }
}