洛谷 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}。

#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; }