반응형
https://www.acmicpc.net/problem/17352
17352번: 여러분의 다리가 되어 드리겠습니다!
선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다. 어제까지는 그랬다. "왜 다리
www.acmicpc.net
[ 문제풀이 ]
1. 부모 노드를 저장할 vect 배열을 선언합니다.
2. vect[ i ] = i 로 초기화합니다.
3. Union-Find를 활용하여 다리를 이어주고, 부모 노드의 값이 1과 다른 다리를 1과 함께 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include<iostream> using namespace std; int N; int vect[300001]; int Find(int num) { if (vect[num] == num) return num; return vect[num] = Find(vect[num]); } void Union(int a, int b) { int pa = Find(a); int pb = Find(b); vect[pb] = pa; } int main() { scanf("%d", &N); for (int i = 1; i <= N; i++) { vect[i] = i; } for (int i = 0; i < N - 2; i++) { int a, b; scanf("%d %d", &a, &b); if (Find(a) != Find(b)) { Union(a, b); } } for (int i = 2; i <= N; i++) { if (Find(1) != Find(i)) { printf("1 %d", i); return 0; } } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 20955번 - 민서의 응급 수술 (C++) (0) | 2023.05.31 |
|---|---|
| [ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++) (0) | 2023.05.30 |
| [ 백준 ] 12899번 - 데이터 구조 (C++) (0) | 2023.05.28 |
| [ 백준 ] 18116번 - 로봇 조립 (C++) (0) | 2023.05.27 |
| [ 백준 ] 11376번 - 열혈강호 2 (C++) (0) | 2023.05.26 |