알고리즘 문제/BOJ
17352번 여러분의 다리가 되어 드리겠습니다!
parkit
2019. 8. 19. 10:51
728x90
반응형
https://www.acmicpc.net/problem/17352
유니온-파인드(union-find) 문제이다.
주의할 것은 parent[i]와 getParent(i)를 구별하는 것이다.
parent[i] : i의 부모 노드(번호)
getParent(i) : i의 루트 노드(번호)
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 <bits/stdc++.h> using namespace std; int n, parent[300003]; int getParent(int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent[x]); } void unionParent(int a, int b) { a = getParent(a); b = getParent(b); if (a < b) parent[b] = a; else parent[a] = b; } int main(void) { int left, right; scanf("%d", &n); for (int i = 1; i <= n; i++) parent[i] = i; for (int i = 0; i < n - 2; i++) { scanf("%d %d", &left, &right); unionParent(left, right); } for (int i = 1; i <= n - 1; i++) if (getParent(i) != getParent(i + 1)) { printf("%d %d\n", i, i + 1); return 0; } return 0; } | cs |
728x90
반응형