并查集

并查集模板

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return

        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1


n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    z, x, y = map(int, input().split())
    x -= 1
    y -= 1
    if z == 1:
        uf.union(x, y)
    else:
        if uf.find(x) != uf.find(y):
            print('N')
        else:
            print('Y')