본문 바로가기

파이썬

[백준 파이썬] 1717번 집합의 표현

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

 

<코드>

import sys
input = sys.stdin.readline

def find_set(x):
    if p[x] == x:
        return x
    parent = find_set(p[x])
    p[x] = parent
    return parent

def union(a, b):
    p_a = find_set(a)
    p_b = find_set(b)
    p[p_b] = p_a


n, m = map(int, input().split())
p = [i for i in range(n+1)]
for _ in range(m):
    a, b, c = map(int,input().split())
    if a == 0:
        union(b,c)
    elif a == 1:
        if find_set(b) == find_set(c):
            print('YES')
        else:
            print('NO')

 

<풀이과정>

union-find 알고리즘으로 풀어야되는데 몰라서 구글링 + 유명 블로그를 참고하였다.