[백준 1717] 집합의 표현

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

 

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

 

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

---

접근

입력받는 a와 b를 합칠 때 b의 루트 노드를 a로 설정한다.

초기에는 각 번호가 자기자신을 루트 노드로 설정하고 있으며 합치는 명령이 있을 때 b의 루트노드를 a로 설정하고 a와 b가 공통된 루트노드를 가지고있는지는 각각의 인덱스를 확인해본다.

 

구현

초기에 자기자신을 루트노드로 설정한다.

p = [n for n in range(N+1)]

 

입력받은 노드의 대표노드를 찾는다.

만약 자기자신이 아니라면 현재 대표노드로 설정된 것을 거슬러올라가 루트노드를 설정해준다.

def find_set(a):
    if p[a] == a:
        return a
    else:
        b = find_set(p[a])
        p[a] = b
        return b

 

이제 두 개의 번호를 합칠 때는 대한 루트노드를 찾고 b의 루트노드를 a의 루트노드로 설정한다.

def union(a, b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        p[b] = a

---

전체 코드

import sys
input = sys.stdin.readline

def find_set(a):
    if p[a] == a:
        return a
    else:
        b = find_set(p[a])
        p[a] = b
        return b

def union(a, b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        p[b] = a

N, M = map(int, input().split())
p = [n for n in range(N+1)]

for _ in range(M):
    command, a, b = map(int, input().split())

    if command == 0:
        union(a, b)
    else:
        if find_set(a) != find_set(b):
            print("NO")
        else:
            print("YES")