2025年3月8日米哈游机试第三题也可以使用并查集解决
并查集(Union-Find)是一种树型数据结构,它的作用是管理元素所属集合的数据结构,主要支持两个操作:
从代码实现来说:
如题,现在有一个并查集,你需要完成合并和查询操作。
第一行包含两个整数 N,M ,表示共有 N 个元素和 M个操作。
接下来 M 行,每行包含三个整数 Zi,Xi,Yi 。
1<=N,M<=105
对于每一个 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