题解 | 并查集的实现

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
parent=[i for i in range(n+1)]
size=[1]*(n+1)
def find(x):
    stack=[]
    while x!=parent[x]:
        stack.append(x)
        x=parent[x]
    while stack:
        parent[stack.pop()]=x
    return x
def isSameSet(x,y):
    return find(x)==find(y)
def union(x,y):
    fx=find(x)
    fy=find(y)
    if fx!=fy:
        if size[fx]>=size[fy]:
            size[fx]+=size[fy]
            parent[fy]=fx
        else:
            size[fy]+=size[fx]
            parent[fx]=fy
for _ in range(m):
    opt,x,y=map(int,input().split())
    if opt==1:
        if isSameSet(x,y):
            print("Yes")
        else:
            print("No")
    else:
        union(x,y)