백준 1717번 집합의 표현

정보

문제 바로가기 [클릭]

난이도: Gold4

관련 개념: #분리 집합 #자료구조

---

조건

시간 제한	메모리 제한
1초	128 MB

---

문제

초기에 {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

출력

NO
NO
YES

---

코드(파이썬)

import sys


sys.setrecursionlimit(10**6)

def find(num):
    if sets[num] != num:
        sets[num] = find(sets[num])
    return sets[num]

def union(num1, num2):
    set1 = find(num1)
    set2 = find(num2)
    
    if set1 != set2:
        if set1 < set2:
            sets[set2] = set1
        else:
            sets[set1] = set2
            
n, m = map(int, sys.stdin.readline().split())
sets = list(range(n+1))

for _ in range(m):
    op, num1, num2 = map(int, sys.stdin.readline().split())
    if op:
        print("YES" if find(num1) == find(num2) else "NO")
    else:
        union(num1, num2)

---

특이사항

• 해결방식
  • 기존의 리스트 이용 집합 표현 방식 사용
  • find 함수에서 시간이 다수 소요
  • 각 집합이 가리키는 노드를 하나로 갱신하는 방법을 이용해 시간 단축

---

참고문헌

• 문병로, 쉽게 배우는 알고리즘 :관계 중심의 사고법, 문병로, 2018