现在有一个并查集,你需要完成合并和查询操作。
输入格式:
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。
接下来 M 行,每行包含三个整数 zi,xi,yi 。
当 zi=1 时,将 xi与yi所在的集合合并。
当 zi=2 时,输出xi与yi 是否在同一集合内,是的输出 Y ;否则输出 N.
输出格式:
对于每一个zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N 。
输入样例:
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出样例:
N
Y
N
Y
#include<iostream>
using namespace std;
const int N = 2e5 + 10;
int fa[N];
int n, m, p1, p2, p3;
int find(int k)
{if (fa[k] == k)return k;return fa[k] = find(fa[k]);
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){fa[i] = i;}for (int i = 1; i <= m; i++){cin >> p1 >> p2 >> p3;if (p1 == 1){fa[find(p2)] = find(p3);}elseif (find(p2) == find(p3))printf("Y\n");elseprintf("N\n");}return 0;
}