알고리즘 스터디 - 백준 1717번 : 집합의 표현

문제 해석

• 초기 0~n까지의 숫자가 각각 총 n+1개의 집합을 이루고 있을 때 2가지 연산을 진행함

1) 합집합 연산 - 0 a b 형태로 주어짐
2) 두 원소가 같은 집합에 포함되어 있는지 확인 - 1 a b의 형태로 이루어짐

• 이 문제 같은 경우 집합을 사용하여 직접 연산을 할 수 있지만 각 집합마다 루트가 뭔지 모르는 경우가 있기에 유니온-파인드를 사용한다.

1) 합집합은 유니온으로 대응하여 루프 노드를 통일
2) 같은 집합 여부는 파인드로 대응하여 루프 노드가 다르면 NO 같으면 YES를 함

알고리즘 코드

• 시간초과가 많이 발생한 문제로 이를 해결하기 2가지를 했다.

1) sys.setrecursionlimit(1000000) 설정
2) parent[x] = find_parent(parent[x])로 find 함수 변경

• 2번 사항은 내가 잘못 알고 있던 것일 수도 있다.

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_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union(x, y):
    x = find_parent(x)
    y = find_parent(y)

    if x < y:
        parent[y] = x
    else:
        parent[x] = y

for _ in range(m):
    calculate, x, y = map(int, input().split())

    if calculate == 0:
        union(x, y)
    else:
        root_x = find_parent(x)
        root_y = find_parent(y)

        if root_x == root_y:
            print("YES")
        else:
            print("NO")