백준 - 여러분의 다리가 되어 드리겠습니다!(17352) 본문
union find를 이용해서
부모 노드를 계속 갱신해 주고
나중에 set로 출력해 준다.
def find_(start):
if cost[start] == start:
return start
cost[start] = find_(cost[start])
return cost[start]
def union_(a,b):
data_a = find_(a)
data_b = find_(b)
if data_a < data_b:
cost[data_b] = data_a
else:
cost[data_a] = data_b
n = int(input())
data = []
cost = [i for i in range(n+1)]
for _ in range(n-2):
a,b= list(map(int, input().split()))
union_(a,b)
for i in range(n):
find_(i)
cost_set = set(cost[1:])
print(list(cost_set)[0], list(cost_set)[1])
'알고리즘' 카테고리의 다른 글
백준 - 가장 긴 증가하는 부분 수열5(14003) (0) | 2023.12.12 |
---|---|
백준 - 선분 그룹(2162) (0) | 2023.12.12 |
백준 - 롤러코스터(2873) (1) | 2023.12.12 |
백준 - 라면사기(18185) (0) | 2023.12.09 |
백준 - 평범한 배낭(12865) (1) | 2023.11.30 |
Comments