[백준] 16562번: 친구비

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

initial

Union find was 100% definitely but i was gonna use dfs to explore each possibility of combination whose sum doesnt exceed k. But this has some issues.

1) We only want to add the parent’s cost, not the children so we need some visited list to do this?

2) If this particular is a disjoin set(i.e. Not linked to any other nodes but itself which means parent is itself), we have no choice but to buy this separately. If however if we dont have enough money, that is an invalid case.

In substitute, I found an easy way of using a set where if we have not seen this node’s parent before, we add that parent to the set and increment via the parent’s cost. But i think this way 2) isnt being considered properly?

wrong at 29%

import sys
input=sys.stdin.readline
n, m, k = map(int, input().split())
parent = [i for i in range(n + 1)]
lst = [0] + list(map(int, input().split()))

def find_parent(node, parent):
    if parent[node] != node:
        parent[node] = find_parent(parent[node], parent)
    return parent[node]

def union(node1, node2, parent):
    par1 = find_parent(node1, parent)
    par2 = find_parent(node2, parent)
    if lst[par1] < lst[par2]:
        parent[par2] = par1
    else:
        parent[par1] = par2
        
for _ in range(m):
    a,b=map(int, input().split())
    union(a,b,parent)

ans = 0
check = set()
for i in range(1, n+1):
    if parent[i] not in check:
        ans += lst[parent[i]]
        check.add(parent[i])

if ans > k:
    print('Oh no')
else:
    print(ans)