사이클 게임 20040

문제

접근 방법

유니온 파인드를 활용하여 하나씩 같은 집합에 넣어준다. 넣어주기 전에 찾기를 활용하여 같은 루트에 있는 것이 확인되면 그 값을 출력해준다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> parents;
int find(int num)
{
    if (parents[num] == num)
        return num;
    return parents[num] = find(parents[num]);
}
void merge(int num1, int num2)
{
    num1 = find(num1);
    num2 = find(num2);
    if (num1 > num2)
    {
        parents[num2] = num1;
    }
    else
    {
        parents[num1] = num2;
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, ret = 0, p1, p2;
    cin >> n >> m;
    parents = vector<int>(n);
    for (int i = 0; i < n; ++i)
    {
        parents[i] = i;
    }
    for (int i = 1; i <= m; ++i)
    {
        cin >> p1 >> p2;
        p1 = find(p1);
        p2 = find(p2);
        if (p1 == p2)
        {
            ret = i;
            break;
        }
        merge(p1, p2);
    }
    cout << ret;
}

풀이

제출했을 때 시간이 오래 걸려서 실수했나 싶었다. 다른 사람의 풀이를 보니 입력을 다 안 받고 반환하거나 반복문을 나오는 형식으로 이루어진 것을 확인했다. 일반적으로 입력은 다 받아야 하기에 안 했던 행동인데 백준에서는 허용되는 것 같다.
실제로 그렇게 수정하고 제출하니 230ms에서 100ms로 줄어들었다.