[백준] 20040. 사이클 게임 - Python

[Gold IV]

 

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

20040번: 사이클 게임

 

풀이

Union-Find를 이용한, 서로소 집합(Disjoint Set) 문제.

 

Union-Find를 잘 구현하고, 이를 이용해 사이클이 생겼는 지를 각 반복마다 확인하면 된다.

Union-Find 알고리즘을 알고 있다면 다른 설명이 필요하지 않으므로, 생략.

 

AC.

from collections import deque
n, m = map(int, input().split())

root = {i: i for i in range(n)}

def find(x):
    if root[x] == x:
        return x
    else:
        # 경로 압축
        root[x] = find(root[x])
        return root[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x > y:
        root[x] = y
    else :
        root[y] = x

for i in range(m):
    a, b = map(int, input().split())
    if find(a) == find(b):
        print(i+1)
        break
    union(a, b)
else:
    print(0)