[백준-20040] 사이클 게임

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

20040번: 사이클 게임

 

union_find 이거 하나만 알면 풀 수 있는 문제이지 않을까 한다.

시간복잡도에 대해 알아보면 1초의 시간 제한이 있고, 입력된 선분 정보의 개수가 100만개이므로 최소 nlog(n) 의 시간복잡도로 풀어야 통과가 되는 문제이다. 이에 따라 바로 로직을 알아보면 다음과 같다.

1. 입력받은 n 만큼 root 배열을 초기화 시켜준다.
2. 하나씩 입력 받을 때마다 root 배열을 통해 set_union 해준다. (하나로 합쳐준다.)
3. 합쳐줄 때 이미 같은 root 를 가지고 있었을 경우 바로 해당 index 를 출력하고 프로그램을 끝낸다.

위 로직으로 풀면 트리 형태의 union_find 알고리즘으로 인해 선분 하나씩 입력할 때마다 평균 log(n)의 복잡도가 생기게 되어 총 nlog(n) 의 복잡도로 간단하게 풀린다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef tuple<int, int, string> tii;
int root[500001];
int find_union(int a) {
    if (root[a] == a)
        return a;
    else {
        return find_union(root[a]);
    }
}
bool set_union(int a, int b) {
    int x = find_union(a);
    int y = find_union(b);
    if (x == y) return false;
    if (x < y) root[y] = x;
    else root[x] = y;
    return true;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, a, b;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        root[i] = i;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        if (!set_union(a, b)) {
            cout << i;
            break;
        }
        if (i == m) {
            cout << 0; 
            break;
        }
    }

    return 0;
}