题目背景
本题数据范围已经更新到 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操作会陷入死循环或访问越界。
C. 输出优化
在算法竞赛中，当输出行数非常多（例如10^5行）时：
cout<<endl：会强制刷新缓冲区，速度慢。cout << "\n"：仅换行，速度快。
建议习惯性使用 \n。
4. 应用场景
并查集不仅用于判断连通性，还是很多高级算法的基石：
图论判环：加边时，如果两个点已经在一个集合里，说明形成了环。
Kruskal 算法：最小生成树的核心，利用并查集判断边是否连接了两个不同的连通块。
连通块数量统计：最后遍历一遍
fa数组，统计fa[i]==i的个数。
