[Python] 백준 20040 사이클 게임

20040번: 사이클 게임

유니온 파인드

처음 파이썬으로 돌렸을 때 런타임 에러가 났다. for문에서 find함수 사용을 없애고, union함수 내에서 인덱스 값을 저장하도록 했다. 그리고 합칠 때 부모의 최솟값으로 통일 되게 했는데 이렇게 안하면 런타임 에러가 났다.

 

1) 입력 받은 두 개의 점을 유니온 함수로 합친다.

2) 두개의 점의 부모가 다르면 합치고, 부모가 같으면 게임 끝.

3) 최초의 게임 끝일 때의 인덱스 값을 endgame에 저장하고 출력. 

 

전체 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
parents = [i for i in range(n)]
endgame = 0

def find(x):
    if x == parents[x]:
        return x
    else:
        y = find(parents[x])
        parents[x] = y
        return y

def union(x, y, indx):
    global endgame
    x = find(x)
    y = find(y)
    if x != y:
        parents[max(x,y)] = min(x,y)
    elif endgame == 0:
        endgame = indx

for i in range(m):
    a, b = map(int, input().split())
    union(a, b, i + 1)

print(endgame)