[BOJ] [Python] 16562 : 친구비

Union-Find 알고리즘으로 해결했다.

 

친구비가 큰 노드가 작은 노드 쪽으로 들어간다.

 

만약 친구비가 같다면, 트리의 높이를 따진다.

트리의 높이가 작은 쪽이 긴 쪽으로 들어간다.

 

 

n, m, k = map(int, input().split())

cash = [0]
cash += list(map(int, input().split()))

parent = [i for i in range(0, n + 1)]
rank = [0] * (n + 1)  # 트리 높이


def find(x):
    if x == parent[x]:
        return x

    else:
        y = find(parent[x])
        parent[x] = y

        return y


def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    if cash[x] < cash[y]:
        a, b = y, x

    elif cash[y] < cash[x]:
        a, b = x, y

    else:
        if rank[x] < rank[y]:
            a, b = y, x

        else:
            a, b = x, y

        if rank[x] == rank[y]:
            rank[b] += 1

    parent[a] = b


for _ in range(m):
    v, w = map(int, input().split())

    union(v, w)

result = 0
dp = [0] * (n + 1)

for n in range(1, n + 1):
    num = find(n)

    if dp[num] == 0:
        dp[num] = 1
        result += cash[num]

if k < result:
    print("Oh no")

else:
    print(result)

 

 

n개의 원소에 대해 Union-Find를 M번 수행했을 때 

평균 시간 복잡도는 O(MlogN)이다.