Union Find

한음·2022년 2월 23일
0
post-thumbnail

관련문제
백준#1717 - 집합의 표현

import sys


n, m = map(int, sys.stdin.readline().split())

root = []
rank = []


def find(x):
    if root[x] == x:
        return x
    else:
        root[x] = find(root[x])
        return find(root[x])


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] > rank[y]:
        root[y] = x
    else:
        root[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


for i in range(n + 1):
    root.append(i)
    rank.append(0)
for _ in range(m):
    op, a, b = map(int, sys.stdin.readline().split())
    if op == 0:
        union(a,b)
    else:
        a = find(a)
        b = find(b)
        if a == b:
            print("YES")
        else:
            print("NO")

조건을 잘읽자
집합 n+1 개

백준은 이상한데서 열받는다

profile
https://github.com/0hhanum

0개의 댓글