[백준] 20040번 사이클 게임 C++ 문제풀이

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

20040번: 사이클 게임

문제 풀이

맨 처음에 문제를 보자마자 이전에 풀었던 9466번 텀프로젝트 문제가 생각이 났다.

그래프 탐색 + 몇 번째에 사이클 완성되는지를 중점으로 코드를 작성했으나, 양방향 그래프이다 보니 사이클 찾는게 쉽지 않았고, 사이클을 찾는 코드를 작성했는데 시간복잡도가 매우 컸다.

 

다른 블로그 글들을 찾아보니, 그래프에 사이클이 있는지 여부를 판단하는 알고리즘에는

1) 무방향 그래프에서 사이클 찾기 => Union-Find 알고리즘을 이용

2) 방향 그래프에서 사이클 찾기 => DFS 탐색 알고리즘 이용

한다고 하더라....

 

20040번의 문제의 경우에는 무방향 그래프이니 Union-Find 알고리즘을 이용해야 하는구나를 알게되었다.

Union-Find 알고리즘의 이론의 경우 아래 블로그를 참고했고, 코드의 경우 

https://lordofkangs.tistory.com/340

[Algorithm] 무방향그래프에서 싸이클 찾기

코드의 경우 아래 블로그를 참고했다.

https://cocoon1787.tistory.com/426 

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

소스 코드

#include <iostream>
using namespace std;

int n, m;
int parent[500001] = { 0 };
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;

}