백준 1717 : 집합의 표현 (Python)

본문 링크

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def Find(x):

    if Disjoint[x]!=x:
        Disjoint[x]=Find(Disjoint[x])
    return Disjoint[x]

def Union(A,B):

    A=Find(A)
    B=Find(B)

    if A<B:
        Disjoint[B]=A #더 작은 값을 넣어주어야함.
    else:
        Disjoint[A]=B


N,M=map(int,input().split())
Disjoint=[0]*(N+1)

for i in range(1,N+1):
    Disjoint[i]=i



for i in range(M):

    print(Disjoint)
    K,A,B=map(int,input().split())
    if K==0:
        Union(A,B)
    else:
        if Find(A)==Find(B):
            print("YES")
        else:
            print("NO")

📌 어떻게 접근할 것인가?

유니온 파인드 기초 문제입니다. 유니온 파인드 알고리즘에 대해서는 이전에 유니온 파인드 - Union Find 이 글에서 다뤘던 적이 있습니다.

일단 유니온 파인드를 수행하기 전에 배열을 만들고 모든 노드가 자신의 번호를 가르키도록 합니다.
이후 $Find$ 함수를 만들어 주고 $Union$ 함수도 만들어 줍니다.

총 $M$ 번의 쿼리가 주어지는데 $K$ 가 0 일때는 두 노드를 합치면 되고 1 일때는 $Find(A)==Find(B)$ 를 통해서 같은 집합에 속하는지 판별 해줍니다.