1717. 집합의 표현

https://www.acmicpc.net/problem/1717

문제 해석

• 합집합과 같은 집합인지 확인하는 문제로 분리집합(Union-Find)의 대표적인 문제이다.

 

구현 방법

• 총 3단계로 나누어 구현
  1. Root를 저장할 배열 초기화
  2. Find 함수 작성
     • 같은 Root를 가지고 있는지 확인( 같은 집합인가 확인)
  3. Union 함수 작성
     • 서로 다른 두 집합을 합집합 (Root 를 같게 함)
     • 이미 같으면 할 필요 없음

코드

# 1717 집합의 표현
import sys
input = sys.stdin.readline

def find(num:int)->int:
    if parent[num] == num:
        return num
    parent[num] = find(parent[num])
    return parent[num]


def union(num1:int, num2:int) -> None:
    x = find(num1)
    y = find(num2)
    if x != y:
        parent[y] = x
    return


def solution(n:int, m:int) -> None:
    for _ in range(m):
        order, a, b = map(int, input().split())
        if order:       # 같은 집합인가 확인
            if find(a) == find(b):
                print("yes")
            else:
                print("no")
        else:           # 합집합
            union(a, b)
    return


if __name__ == "__main__":
    # input
    n, m = map(int, input().split())
    parent = [i for i in range(n+1)]
    solution(n, m)