[백준] 13306 - 트리

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

13306번: 트리

 

일반적인 방법으로 UNION-FIND TREE 를 사용할 경우 edge 삭제 후 부모 갱신 과정에서 시간초과가 발생한다. 삭제된 edge 의 하위에 있는 노드의 모든 부모를 갱신해야 하므로 오버헤드가 크다.

 

edge 를 추가하며 부모를 갱신할 경우, 앞선 경우에서의 오버헤드를 줄일 수 있다.

단, 결과가 반대로 얻으므로 저장 후, 역순으로 출력해야 한다.

 

<python 코드>

import sys
 
inp = sys.stdin.readlines()
n, q = tuple(map(int, inp[0].split()))
parent = [i for i in range(n+1)]
result = []
 
for q in inp[n:][::-1]:
    q = q.split()
    if len(q) == 2:
        parent[int(q[1])] = int(inp[int(q[1]) - 1])
    else:
        a, b = int(q[1]), int(q[2])
        p_a, p_b = parent[a], parent[b]
        while(True):
            if parent[p_a] == p_a:
                parent[a] = p_a
                break
            p_a = parent[p_a]
        while(True):
            if parent[p_b] == p_b:
                parent[b] = p_b
                break
            p_b = parent[p_b]
        
        if p_a == p_b:
            result.append(True)
        else:
            result.append(False)
 
for re in result[::-1]:
    if re:
        print('YES')
    else:
        print('NO')