题目背景
本题数据范围已经更新到 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}。
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int fa[N]; int find(int x) { if(fa[x]==x) return x; else return fa[x]=find(fa[x]); } int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) fa[i]=i; while(m--) { int z,x,y; cin>>z>>x>>y; if(z==1) { int fx=find(x); int fy=find(y); fa[fx]=fy; }else{ if(find(x)==find(y)) cout<<"Y"<<endl; else cout<<"N"<<endl; } } return 0; }
