백준 20040 사이클 게임 - C++, Disjoint Set

20040번: 사이클 게임

#include <iostream>
using namespace std;

int parent[500001];
int n, m;

int FindParent(int x){
    if(x == parent[x])
        return x;
    else
        return parent[x] = FindParent(parent[x]);
}

void Merge(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return;
    parent[x] = y;
    return;
}

int main(){
    scanf("%d %d", &n, &m);

    for(int i = 0; i < n; i++)
        parent[i] = i;
    
    for(int i = 1; i <= m; i++){
        int a, b;
        scanf("%d %d", &a, &b);

        if(FindParent(a) == FindParent(b)){
            printf("%d\n", i);
            return 0;
        }
        Merge(a, b);
    }
    printf("0\n");
    return 0;
}

---

 사이클의 유무를 판단하기 위해 연결된 노드들간 부모를 비교하는 작업을 처리해 줬습니다. 부모가 다르다면 병합을 해주고 만약 같다면 사이클이 일어난 것이니 해당하는 i를 출력한 뒤 종료하면 됩니다.

 

 다른 사람들의 코드와 비교해 시간이 많이 나온 편인데 다른 빠른 코드들을 보면서 파악을 해봐야할 문제입니다.