[ 17352 ] [ Union-Find ] 여러분의 다리가 되어 드리겠습니다

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

17352번: 여러분의 다리가 되어 드리겠습니다!

 

---

풀이 과정

---

1. 문제에서 다리를 하나 무너뜨려 서로 왕복할 수 없는 섬이 생겼다고 주어졌으므로 두개의 섬으로 분리되었다는걸 알 수 있음.
2. Union-Find 알고리즘을 사용하여 두개의 섬의 집합을 구해준다.
   1. 이어진 섬의 parent는 같으며, 이어지지 않은 섬의 parent는 다르다는 점을 이용하여 1번째 섬에서부터 N번째 섬까지 방문하면서 인접한 섬과의 parent를 비교한다.
   2. parent 값이 다른 경우 떨어진 섬이므로 두 섬을 연결해주면 된다.

---

소스 코드

---

import sys

sys.setrecursionlimit(10**5)
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
parent = [i for i in range(N+1)]


def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    par1 = find(parent, a)
    par2 = find(parent, b)

    if par1 != par2:
        parent[par1] = par2

for _ in range(N-2):
    a, b = map(int, input().split())
    if find(parent, a) != find(parent, b):
        union(parent, a, b)

for i in range(2, N+1):
    if find(parent, i) != find(parent, i-1):
        union(parent, i, i-1)
        print(i, i-1)