【模板】并查集
题目描述
如题,现在有一个并查集,你需要完成合并和查询操作。
输入格式
第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作。
接下来 $M$ 行,每行包含三个整数 $Z_i,X_i,Y_i$ 。
当 $Z_i=1$ 时,将 $X_i$ 与 $Y_i$ 所在的集合合并。
当 $Z_i=2$ 时,输出 $X_i$ 与 $Y_i$ 是否在同一集合内,是的输出
Y
;否则输出 N
。
输出格式
对于每一个 $Z_i=2$ 的操作,都有一行输出,每行包含一个大写字母,为 Y
或者 N
。
样例 #1
样例输入 #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
提示
对于 $30\%$ 的数据,$N \le 10$,$M \le 20$。
对于 $70\%$ 的数据,$N \le 100$,$M \le 10^3$。
对于 $100\%$ 的数据,$1\le N \le 10^4$,$1\le M \le 2\times 10^5$,$1 \le X_i, Y_i \le N$,$Z_i \in \{ 1, 2 \}$。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 50;
int n, m;
int fa[N];
int find(int x)
{
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void unionset(int x, int y)
{
fa[find(x)] = find(y);
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
fa[i] = i;
while(m -- )
{
int z, x, y;
scanf("%d %d %d", &z, &x, &y);
if(z == 1) unionset(x, y);
if(z == 2)
{
x = find(x), y = find(y);
if(x == y) puts("Y");
else puts("N");
}
}
return 0;
}