[백준/1717/파이썬] 집합의 표현

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

1717번: 집합의 표현

Problem

• 초기에 {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이며 같을 수도 있다.

SOL

유니온 -파인드 구조를 구현할 수 있는지 묻는 전형적인 문제이다.  유니온 -파인드 구조를 써야겠다고 알수 있다면 아주쉽게 구현할 수 있는 문제임!

# Union-Find/disjoint set
import sys
input= sys.stdin.readline
sys.setrecursionlimit(10**6)
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[a]=b

N,M =map(int,input().split())
parent=[x for x in range(N+1)]

for i in range(M):
    cmd,a,b=map(int,input().split())
    #find
    if cmd:
        print("YES") if find(a)==find(b) else print("NO")
        continue
    #union
    union(a,b)