-
[BOJ 20040, C++] 싸이클 게임알고리즘/BOJ 2021. 9. 8. 18:21반응형
https://www.acmicpc.net/problem/20040
풀이
문제만 읽으면 어떤 알고리즘을 써야하는지 이해가 잘 안되지만, 예제를 직접 그림으로 그려보면서 파악해보면 바로 유니온파인드(분리집합) 알고리즘을 사용해야 한다는 것을 알 수 있습니다.
사이클을 만들어지는 조건이 두 점의 번호가 같은 선으로 이어져 있을 경우니까요.
n의 값이 500,000이기 때문에 파이썬은 sys.setrecursionlimit(500000)을 사용해야 아마 통과할 것 같습니다.
코드
123456789101112131415161718192021222324252627282930313233343536#include <iostream>#include <cstring>using namespace std;using ll = long long;const int N = 500001;int n, m, a, b, ans = 0;int p[N];int find(int x) {if (p[x] == x) return x;p[x] = find(p[x]);return p[x];}void merge(int x, int y) {x = find(x);y = find(y);p[y] = p[x];}int main(){ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for (int i = 0; i < n; i++) p[i] = i;for (int i = 0; i < m; i++) {cin >> a >> b;if (ans == 0 && find(a) == find(b)) ans = i + 1;merge(a, b);}cout << ans << endl;}cs 반응형'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ 20041, Python 3] Escaping (0) 2021.09.09 [BOJ 20046, Python 3] Road Reconstruction (0) 2021.09.08 [BOJ 20044, Python 3] Project Teams (0) 2021.09.08 [BOJ 15906, Python 3] 변신 이동 게임 (0) 2021.09.08 [BOJ 22984, Python 3] 반짝반짝 2 (0) 2021.09.06