백준 20040 사이클 게임 혼내주기

 

이 문제는 작년 PS를 시작하기 전 ICPC 예선에서 0솔을 하면서 봤던 문제 중 하나다. 그땐 보자마자 brute force로 다 확인하는 알고리즘으로 짜서 틀렸고, 어떻게 푸는지 감도 못잡았다. 다시 보니 유니온 파인드를 이용하는 것만 발견하면 간단한 문제다.

 

#include <iostream>
using namespace std;

int parent[500000];

int find(int u){
    if(u == parent[u]) return u;
    return parent[u] = find(parent[u]);
}

bool merge(int u, int v){
    u = find(u); v = find(v);
    if(u == v) return true;
    parent[u] = v;
    return false;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, a, b; cin >> n >> m;
    for(int i = 0; i < n; ++i) parent[i] = i;

    for(int i = 0; i < m; ++i){
        cin >> a >> b;
        if(merge(a, b)){
            cout << i+1;
            return 0;
        }
    }
    cout << 0;
}