1717 - 집합의 표현

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

이 전에 풀었던 1976 - 여행 가자 문제와 유사한 문제입니다.

 

단, 이 문제는 중간 중간마다 결과를 출력해야 한다는 점만 분기를 주면 되는 문제입니다.

 

이 문제도 Union-Find 알고리즘을 사용하면 쉽게 풀 수 있는 문제입니다.

 

import sys

sys.setrecursionlimit(10**9)

def find(u):
    if u == parent[u]:
        return u
    else:
        parent[u] = find(parent[u])
        return parent[u]

def union(u, v):
    u = find(u)
    v = find(v)

    if u == v:
        pass
    else:
        if u < v:
            parent[v] = u
        else:
            parent[u] = v

N, M = list(map(int,input().split()))

parent = [i for i in range(N + 1)]

for _ in range(M):
    a, u, v = list(map(int,input().split()))
    if a == 0:
        union(u, v)
    else:
        c1 = find(u)
        c2 = find(v)
        if c1 == c2:
            print("YES")
        else:
            print("NO")

---

이상 1717 - 집합의 표현 였습니다. ^_^