[알고리즘] 백준 20040 - 사이클 게임 (C++)

[문제 링크] : https://www.acmicpc.net/problem/20040

#include <iostream>
#include <vector>
using namespace std;

int N, M;
int Arr[500001];
int Ans;

int find(int n){
    if(Arr[n] == n){
        return n;
    }
    else{
        return Arr[n] = find(Arr[n]);
    }
}

bool solve(int a, int b){
    a = find(a);
    b = find(b);

    if(a == b){
        return true;
    }
    else{
        Arr[a] = b;
        return false;
    }
}

int main(){
    cin >> N >> M;
    for(int i=0; i<N; i++){
        Arr[i] = i;
    }

    int a, b;
    for(int i=1; i<=M; i++){
        cin >> a >> b;
        if(solve(a, b) == true){
            Ans = i;
            break;
        } 
    }

    if(Ans == 0){
        cout << 0 << "\n";
    }
    else{
        cout << Ans << "\n";
    }
    return 0;
}