【并查集】Python模板

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数 Zi,Xi,Yi 。

当 Zi=1 时，将 Xi 与 Yi 所在的集合合并。

当 Zi=2 时，输出 Xi 与 Yi 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 Zi=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

代码

# 找到最老的祖先
def findroot(x):
    # 如果祖先是自己，则返回自己
    if fa[x] == x:
        return x
    # 递归寻找祖先
    else:
        # 路径压缩
        fa[x] = findroot(fa[x])
        return fa[x]
​
# 合并祖先
def merge(x,y):
    xroot = findroot(x)
    yroot = findroot(y)
    # 如果x和y的祖先不一样，则让x的祖先为y的祖先，这样的话所有指向x的孩子的祖先就都是y了
    fa[xroot] = yroot
    
N,M = map(int, input().split())
# 初始化数组，一开始所有位置的祖先都是自己
fa = [i for i in range(N+1)]
for i in range(M):
    z, x, y = map(int, input().split())
    if z == 1:
        merge(x,y)
    else:
        if findroot(x) == findroot(y):
            print("Y")
        else:
            print("N")
​

https://www.luogu.com.cn/problem/P3367