백준 17352 : 여러분의 다리가 되어 드리겠습니다! (Python)

본문 링크

import sys
input=sys.stdin.readline

def Find(x):

    if disjoint[x]!=x:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

def Union(a,b):

    a=Find(a)
    b=Find(b)

    if a>b:
        disjoint[a]=b
    else:
        disjoint[b]=a


N=int(input())

if N==2:
    print("1 2")
    exit(0)

disjoint=[0]*(N+1)
for i in range(1,N+1):
    disjoint[i]=i


for i in range(N-2):
    a,b=map(int,input().split())
    Union(a,b)

check=set()

for i in disjoint[1:]:

    A=Find(i)

    if A not in check:
        check.add(A)

print(*check)

📌 어떻게 접근할 것인가?

유니온 파인드 기초 문제입니다.
먼저 원래는 모든 다리가 서로 연결되어있습니다. 다만 문제에서 어떤 다리 하나를 잘랐기 때문에
유니온 파인드를 사용하면 서로 다른 집합 2개가 발생합니다.

따라서 유니온 파인드를 실행 해준뒤에 check 라는 $set$ 을 만들어 주어서
서로 다른 집합 2개를 출력해줍니다.