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

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int n, m;
int parent[500000];
int ans;

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

bool union_node(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);

    int u, v;
    cin >> n >> m;

    // 자기 자신을 부모로 지정
    for (int i = 0; i < n; i++)
        parent[i] = i;

    // Union Find
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v;
        if (union_node(u, v))
        {
            ans = i;
            break;
        }
    }

    if (ans == 0) cout << 0;
    else cout << ans;

}

 

풀이 방법

전형적인 유니온 파인드 문제.

find 함수는 부모 노드를 찾는 함수이고
union_node 함수는 두 노드의 부모가 같을 시 true를, 부모 노드가 같지 않을 시 두 노드를 연결하고 false를 반환한다.

union_node 함수를 통해 true가 반환되면 해당 차례를 ans 변수에 저장하고 답을 출력한다.

 

 

www.acmicpc.net/problem/20040

20040번: 사이클 게임