union find
-
[BOJ] 17532 여러분의 다리가 되어 드리겠습니다! - C++개발/알고리즘 & PS 2024. 1. 13. 23:20
https://www.acmicpc.net/problem/17352 17352번: 여러분의 다리가 되어 드리겠습니다!선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다. 어제까지는 그랬다. "왜 다리www.acmicpc.net아이디어n개의 섬이 n-1개의 다리로 모두 이어져 있다가 하나가 끊어졌으므로 2개의 그룹으로 섬을 분류할 수 있다. 각 그룹에서 섬을 하나씩 뽑아 서로 이으면 모든 섬을 다닐 수 있다.여러 섬이 서로 이어져있는지 확인하기 위해 Union-Find를 사용한다. 단계이어진 다리에 대해 Union-Find 수행서로 다른 그룹인 두 섬을 출력하면 되는데 아무 경우..