[백준] 1717번 : 집합의 표현

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

1717번: 집합의 표현

해당 문제는 유니온 파인드 문제로 해결 할 수 있습니다. 집합 a, b 가 주어졌을때 a,b를 합칩니다.

합치는 방법은 유니온 방법으로 합치는데 두개의 집합중 작은 부모노드를 자기자신의 부모노드로 만들면 됩니다.

즉, 부모노드를 동일하게 가져가면 합쳐집니다.

 

해당집합이 서로 속해있지 않는것을 알기위해서는 파인드를 사용합니다. 집합 a, b의 부모노드를 구해보아

부모노드가 같은경우 서로 속해있는 집합이고, 부모노드가 같지 않은경우는 서로소 집합 입니다.

 

경로를 찾을때에는 경로압축 기법을 사용하여 시간복잡도를 단축 할 수 있습니다.

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

parent =[i for i in range(n+1)] # 0부터 N개의 집합을 만들고 부모노드를 가르키는 배열을 만든다.


def union(a,b):
   v1 = getParent(a)
   v2 = getParent(b)
   if v1 > v2: # 값이 큰 값이 작은값의 부모로 들어간다.
       parent[v1] = v2
   else:
       parent[v2] = v1
       
def getParent(a):
    if a != parent[a]:
        parent[a] = getParent(parent[a])
        
    return parent[a]


for _ in range(m):
    op, a, b = map(int, input().split())
    if op == 0: # 0이면 합집합 연산을 수행한다.
        if a != b:
            union(a,b)
    else:
        v1 = getParent(a)
        v2 = getParent(b)
        if v1 != v2: # 부모가 다른경우 공통집합이 아니다.
            print("NO")
        else:
            print("YES")