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

문제링크 : https://www.acmicpc.net/problem/20040

20040번: 사이클 게임

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, result = 0;
int parent[500001];

int find_root(int x)
{
    if(x == parent[x]) return x;  //루트노드면 그대로 반환
    return parent[x] = find_root(parent[x]);  //자식노드면 부모노드로 다시 탐색
}

void Union(int a, int b)
{
    a = find_root(a);
    b = find_root(b);
    if(a!=b)
    {
        parent[a]=b;  //속한 트리가 다르다면 병합시킴 (Union)
    }
}

bool check(int a, int b) //이어졌는가?
{
    a=find_root(a);
    b=find_root(b);
    if(a==b) return 1;
    return 0;
}

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

    cin >> N >> M; 
    int u, v;
    for(int i=0; i<N; i++)
    {
        parent[i]=i;
    }

    for(int i=1; i<=M; i++)
    {
        cin >> u >> v;
        if(check(u, v)) //사이클 유무 확인
        {
            result = i;
            break;
        }
        else Union(u, v);
    }

    cout << (result == 0 ? 0 : result);
    return 0;
}

Union Find의 전형적인 문제이다.

 

먼저 사이클이 완성되었는지 확인하기 위해 현재 입력받은 간선에 대해서 check를 해주고 이어져있다면 사이클이 있는 것이므로 현재 i를 저장하고 종료해준다.

이어져있지 않다면 현재 입력받은 간선에 대해 Union을 진행하고 이후 사이클 유무를 계속해서 탐색한다.

 

result의 값이 초기값 0 그대로 이면 사이클이 없는 것이므로 초기값 그대로 0을 출력하고 사이클이 생겼다면 앞서 저장한 i값이 담긴 result를 력해준다.