[백준 알고리즘] 집합의 표현 - 1717

✏️ 1번째 풀이 방법

0 ~ (n+1) 까지 리스트를 생성한 후 명령어가 0이면 index가 a와 b인 리스트를 서로 복사하는 방법으로 풀이를 생각했다.

import sys
input = sys.stdin.readline

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

hash = [[i] for i in range(n+1)]

for i in range(m):
    op, a, b = map(int, input().split())
    
    if op == 0:
        hash[a].extend(hash[b])
        hash[b].extend(hash[a])
    else:
        if b in hash[a] or a in hash[b]:
            print("YES")
        else:
            print("NO")

❌ 1번째 방법 - 실패

리스트가 a, b는 서로 연결이 되지만 합집합으로는 되지 못하기에 이 방법은 틀렸다.

예) 입력값으로 다음과 같을 때,

7, 3
0 1 2
0 1 3
0 2 4

저장된 리스트

[[0], [1, 2, 3], [2, 1, 2, 4], [3, 1, 2, 3], [4, 2, 1, 2, 4], [5], [6], [7]]

✅ 2번째 방법 - 성공

부모가 누구인지 알 수 있는 함수인 find 함수와
집합을 합쳤을 때, 부모를 같게 만들어주는 union 함수를 따로 정의하여 문제를 풀었다.

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

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

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

def find(x):
    if p[x] == x:
        return x
    p[x] = find(p[x])
    return p[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a <= b:
        p[b] = a
    else:
        p[a] = b

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