1717_집합의 표현

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

1717번: 집합의 표현

 

 

유니온 파인드를 사용하면 어떠한 노드가 그래프에 속해있는지 알 수 있다.

 

 

부모를 찾는 find연산과 유니온 연산으로 나누어져 있다.

 

우선 parents배열을 하나 만들어서 자신의 루트노드를 저장하게 한다. 문제에서 합집합을 만든다는건 결국 두 노드를 이어주어 하나의 그래프로 만든다는 의미이다.

 

그래서 트리구조를 활용해서 가장 부모노드 하나를 잡게한다. 이 노드를 최소값으로 하면 연산량을 더 줄일 수 있다. ( 재귀적으로 호출을 막기 때문 )

 

만약 1-3 이 연결된 상태에서 4를 추가한다면 4의 부모를 3으로 바꿀수도 있지만, 3,4를 모두 1의 자식으로 삼는다면 최종적 부모를 찾기가 더 편할 것이다.

 

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
n,m = map(int,input().split())

parents = [i for i in range(n+1)]
def union(a,b):
    a,b = find(a),find(b)

    if a <= b:
        parents[b] = a
    else:
        parents[a] = b

def find(a):
    if parents[a] ==a:
        return a
    parents[a] = find(parents[a])
    return parents[a]



for _ in range(m):
    order , a , b = map(int,input().split())

    if order:
        print('YES' if find(a)==find(b) else 'NO')
    else:
        union(a, b)