코딩테스트

[BaekJoon 1717번] 집합의 표현 문제(Python)

하루살이 2022. 2. 20. 12:53

집합의 표현 문제입니다.

 

문제링크:https://www.acmicpc.net/problem/1717

 

1717번: 집합의 표현

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는

www.acmicpc.net

 

풀이

union-find 알고리즘을 이용한 문제

 

Code

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

# 부모 테이블 초기화
parent = [i for i in range(n + 1)]

# 부모가 같으면 같은 집합
def find(target):
    if target == parent[target]:
        return target

    parent[target] = find(parent[target])
    return parent[target]

# 합집합
def union(a, b):
    a = find(a)
    b = find(b)

    if not a == b:
        parent[b] = a

for i in range(m):
    x, a, b = map(int, input().split())
    if x == 0:
        union(a, b)
    else:
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")