[BOJ 20040, C++] 싸이클 게임

https://www.acmicpc.net/problem/20040

20040번: 사이클 게임

 

 

풀이

문제만 읽으면 어떤 알고리즘을 써야하는지 이해가 잘 안되지만, 예제를 직접 그림으로 그려보면서 파악해보면 바로 유니온파인드(분리집합) 알고리즘을 사용해야 한다는 것을 알 수 있습니다.

사이클을 만들어지는 조건이 두 점의 번호가 같은 선으로 이어져 있을 경우니까요.

 

n의 값이 500,000이기 때문에 파이썬은 sys.setrecursionlimit(500000)을 사용해야 아마 통과할 것 같습니다.

 

코드

#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;
}