[Algorithm] 20040: cycle_game

📦20040: cycle_game

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-20
문제 확인하기

풀이

• 선분을 그리면서 사이클이 생기는 시기의 차례를 출력하는 문제이다.
• Union Find 방법을 통해서 연결이 안되어 있는 경우 연결시켜주고, 연결이 되어 있는 경우에는 사이클이 만들어진 것이기 때문에 해당 번호를 출력해준다.

#include <iostream>
 
#define endl '\n'
using namespace std;
 
int N, M;
int parent[500001];
int res = 0;
 
void Input(){
    cin >> N >> M;
}
 
int Find(int i){
    if(parent[i]==i) return i;
    else return parent[i] = Find(parent[i]);
}
 
int Union(int i, int j){
    i = Find(i);
    j = Find(j);
    if(i==j) {
        return 1;
    }
    else{
        parent[i] = j;
        return 0;
    }
}
 
void Solution(){
    for(int i=1; i<=N; i++){
        parent[i]=i;
    }
    for(int i=1; i<=M; i++){
        int a, b;
        cin >> a >> b;
        if(Union(a, b)){
            res = i;
            break;
        }
    }
    if(res == 0) cout << 0 << endl;
    else cout << res << endl;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    Input();
    Solution();
 
    return 0;
}