https://www.acmicpc.net/problem/8225
8225번: Tour de Byteotia
In the first line of the standard input there are three integers, n, m, and k (1 ≤ n ≤ 1,000,000, 0 ≤ m ≤ 2,000,000, 1 ≤ k ≤ n), separated by single spaces, that denote, respectively: the number of towns, the number of roads, and the number of
www.acmicpc.net
1부터 k까지의 정점들에 대해, 이 정점을 포함하는 사이클이 없도록 그래프를 재구성해야 한다.
k+1보다 큰 정점들 사이의 간선은 모두 연결해 Union하고, k부터는 사이클이 생기지 않는 간선만 합쳐 준다. (간선에 연결된 두 정점의 분리 집합이 다른 경우) 이보다 많은 간선을 사용하는 방법이 없다는 것은 적당히 생각해 볼 수 있다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 15714 열려라 참깨 (0) | 2023.02.26 |
|---|---|
| 백준 19848 빈 문자열 만들기 (0) | 2023.02.25 |
| 백준 23911 Beauty of tree (0) | 2023.02.16 |
| 백준 4792 레드 블루 스패닝 트리 (0) | 2023.02.15 |
| 백준 15480 LCA와 쿼리 (0) | 2023.02.14 |
