[백준][C++] 20040번: 사이클 게임 <230>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

20040번: 사이클 게임

 

생각의 흐름

대표적인 Union Find 문제인것 같다.

Union Find 알고리즘이 궁금하다면 다음 글을 읽어보길 권장한다.

https://blogshine.tistory.com/103

[알고리즘] Union Find 알고리즘 : 경로 압축

나의 코드

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define MAX 500001

int N, M;
int cnt = 1;
int parent[MAX];

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

bool unionNode(int u, int v)
{
    u = find(u);
    v = find(v);

    // 부모노드가 같으면 사이클이 생기므로 true 반환
    if (u == v) return true;
    else // 노드 결합
    {
        parent[u] = v;
        return false;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        parent[i] = i;
    }
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        if(unionNode(a, b)){
            cout << i+1;
            return 0;
        }
    }
    cout << 0;
    return 0;
}