[백준] 1717번 > 집합의 표현

www.acmicpc.net/problem/1717

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 를 출력해도 된다)

예제 입력 1

7 8

0 1 3

1 1 7

0 7 6

1 7 1

0 3 7

0 4 2

0 1 1

1 1 1

예제 출력 1

NO

NO

YES

 

 

---

풀이

disjoint sets로 해결해야한다. 처음에 직접 append와 pop을 통하여 부분집합을 구현하였는데 시간초과가 발생했다.

리스트를 트리형식으로 구현하여 각각을 부모-자식관계로 연결하려 한다.

또한, 재귀 깊이 제한을 풀어줘야 런타임에러가 발생하지 않는다.(sys.setrecursionlimit(1000000))

다음과 같이 리스트의 각 값을 부모노드로 변경하면서 트리형식으로 연결하며 부분집합을 구하는 것이다.

만약 부모노드가 같다면 같은 집합일 것이고, 부모노드가 다르다면 다른 집합이다.

import sys
sys.setrecursionlimit(1000000)
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 a < b:
        parent[b] = a
    else:
        parent[a] = b

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