【模板】并查集（洛谷P3367）-智慧文博士

题目背景

本题数据范围已经更新到 1≤N≤2×105，1≤M≤106。

题目描述

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

输入格式

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

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

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

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

输出格式

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

输入输出样例

输入 #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

说明/提示

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

对于 35% 的数据，N≤100，M≤103。

对于 50% 的数据，1≤N≤104，1≤M≤2×105。

对于 100% 的数据，1≤N≤2×105，1≤M≤106，1≤Xi,Yi≤N，Zi∈{1,2}。

【算法模板】并查集 (Union-Find)：路径压缩与集合合并

1. 核心概念

并查集是一种用于管理元素所属集合的数据结构，主要支持两种操作：

合并（Union）：将两个不同的集合合并为一个集合。
查询（Find）：查询某个元素属于哪个集合（即寻找该集合的“代表”或“老大”）。

通俗理解

数组fa[i]：记录第i个人的“上级”是谁。
初始化：刚开始每个人都是自己的老大 (fa[i] = i)。
查询 (find)：想知道你是哪个帮派的？就一级一级往上找，直到找到那个“上级是自己”的人，他就是帮主。
路径压缩：找帮主太累了？一旦找到帮主，直接把你的上级改成帮主。以后再问，一步就能找到。
合并 (uni)：两个帮派要合并？让 A 帮派的帮主，认 B 帮派的帮主做老大。

2. 完整代码

#include <bits/stdc++.h> using namespace std; int n,m,z,x,y; int fa[200010];//记录每个节点的父节点 即所在集合的老大 //找老大的过程中进行路径压缩 //即找到x的祖宗节点，并在过程中将x到祖宗路径上所有点的父节点直接设为祖宗 int find(int x){ if(fa[x]==x) return x;//如果自己就是自己老大，返回自己 //这一行完成了在查询过程中进行路径压缩 将最终的老大赋给到路径上每一个元素 else return fa[x]=find(fa[x]); } void uni(int x,int y){ int fax=find(x); int fay=find(y); //如果x和y老大不同 就要合并 让x的老大变成y的老大的老大 if(fax!=fay) fa[fay]=fax; } int main(){ ios::sync_with_stdio(false); cin.tie(0); //初始化所有元素的老大是自己 cin>>n>>m; for(int i=1;i<=n;i++) fa[i]=i; while(m--){ cin>>z>>x>>y; if(z==1){//合并 uni(x,y); } else if(z==2){//查询 //\n代替endl输出更快 if(find(x)==find(y)) cout<<"Y"<<"\n"; else cout<<"N"<<"\n"; } } }

3. 关键细节解析

A. 路径压缩

return fa[x]=find(fa[x]);

这行代码是并查集效率极高的关键。如果不加这一步，树可能会退化成一条长链，查询复杂度变成 O(N)。加上路径压缩后，每次查询都会“压扁”树的高度，平均时间复杂度接近O(1)（准确说是反阿克曼函数 O((N))）。

B. 初始化的时机

很多新手（包括以前的我）容易犯的错误：

// ❌ 错误写法 for(int i=1; i<=n; i++) fa[i]=i; // 此时 n 还是 0！ cin >> n >> m; // ✅ 正确写法 cin >> n >> m; // 先读入 n for(int i=1; i<=n; i++) fa[i]=i; // 再根据 n 初始化

如果顺序反了，fa数组全是 0，后续的find操作会陷入死循环或访问越界。