[백준 BOJ] 20040번 - 사이클 게임 (C++)

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

20040번: 사이클 게임

union-find를 알고있다면 쉽게 풀 수 있는 문제이다. 간략하게 설명하자면, 각 노드는 자신의 부모를 가리키게 되어있는데, 이 때 새로운 두 개의 노드에 대해 같은 부모를 가리키고 있으면 사이클이 형성된다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <vector>

#define endl '\n'
#define ll long long
#define pii pair<int, int>
#define max 987654321

using namespace std;

int n;
int m;
int parent[500001];

int _find(int i)
{
    if (parent[i] == i)
    {
        return i;
    }
    else
    {
        parent[i] = _find(parent[i]);
        return parent[i];
    }
}

void _union(int x, int y)
{
    x = _find(x);
    y = _find(y);
    if (x > y)
    {
        parent[y] = x;
    }
    else
    {
        parent[x] = y;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        parent[i] = i;
    }
    int s, e;
    for (int i = 1; i <= m; i++)
    {
        cin >> s >> e;
        if (_find(s) == _find(e))
        {
            cout << i << endl;
            return 0;
        }
        else
        {
            _union(s, e);
        }
    }
    cout<<0<<endl;
    return 0;
}