백준 20040 사이클 게임

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

20040번: 사이클 게임

본 문제는 전형적인 유니온 파인드 문제이다. 혹시라도 유니온-파인드 알고리즘이 생소하신 분은 이 링크를 참조하여 훑어보기 바란다.

 

유니온-파인드를 이해하고 잘 적용할 수 있다면 비교적 평이한 문제일 수 있지만,

주의해야 할 부분이 있어서 포스팅하게 되었다.

 

파이썬 언어를 사용할 경우, 스택 깊이가 1000으로 기본 설정되어있는데, 이 깊이를 키우기 위해서는 아래와 같이 해야 한다.

sys.setrecursionlimit(10000) <-원하는 수 삽입

유니온-파인드에서 find함수는 보통 아래와 같이 구현된다.

def find(a):
    if root[a]==a:return a
    root[a]=find(root[a])
    return root[a]

여기서 find(root[a])를 하는 부분 때문에 깊이가 깊은 재귀 함수의 형태가 될 수 있는 것이다.

유니온 함수에서 특정 조건을 걸어두지 않고 그냥 연결해주거나 하는 방식을 사용했을 때, 파인드 함수로 루트를 찾아나가다 보면

최악의 경우(worst case) 모든 정점을 한 번씩 다 거치기 때문이다.

 

그래서 유니온-파인드 문제를 파이썬으로 풀 때는 문제에서 주어지는 정점 갯수 등의 조건을 잘 활용하여 그만큼의 재귀 깊이를 확보해두어야 한다. 

 

<주요 알고리즘>

유니온 파인드 (union-find)

 

<코드>

아래에서 보면 정확하게 정점 개수 50만을 주는 것이 아니라 약간의 여유분을 위해 +10을 해주었다.

import sys
si = sys.stdin.readline
sys.setrecursionlimit(500000+10)

n, m = [int(e) for e in si().split()]
assert n<=500000
roots, ans= [i for i in range(n)], 0

def find(a):
    if roots[a] == a:
        return a
    roots[a] = find(roots[a])
    return roots[a]


def union(a, b):
    a,b=find(a),find(b)
    roots[a]=b


for i in range(1, m+1):
    a, b = [int(e) for e in si().split()]
    if find(a) == find(b):
        ans = i
        break
    else:union(a, b)

print(ans)