[Python] 백준 20040번: 사이클 게임

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

20040번: 사이클 게임

1. 플레이어 순서는 중요하지 않고 사이클이 발생하는 시점이 중요하다.

2. 사이클이 발생한다는것은 즉 두 노드의 부모가 같다는 뜻이다.

3. 이미 정답이 나왔으면 더이상 실행할 필요가 없다.

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

def find(x):
    if x == unf[x]:
        return x
    unf[x] = find(unf[x])
    return unf[x]


def union(x, y):
    global i, ans
    x = find(x)
    y = find(y)
    if x == y:
        ans = i + 1
    else:
        if x < y:
            unf[y] = x
        else:
            unf[x] = y

for i in range(m):
    x, y = map(int, sys.stdin.readline().split())
    if not ans:
        union(x, y)

print(ans)