[#알고리즘/Union-Find/기타 그래프 이론/[백준]20040번: 사이클 게임(python)]

Question

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

Solution

앞서 배운 union-find에서 사이클을 판별하는 알고리즘 동작을 그대로 사용한다.

Code

import sys

input = sys.stdin.readline

def find_parent(parent, x) :
    if parent[x] != x :
        parent[x] = find_parent(parent, parent[x])
    return parent[x] 
        
def union_parent(parent, a, b) :
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b :
        parent[b] = a
    else :
        parent[a] = b

n, m = map(int, input().split())

parent = [0] * (n + 1)

for i in range(n) :
    parent[i] = i

# 사이클이 발생한 처례의 번호를 담을 변수 num
num = 0
cycle = False

for i in range(m) :
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 
    if find_parent(parent, a) == find_parent(parent, b) :
        cycle = True
        num = i + 1
        break
    else :
        union_parent(parent, a, b)
        
if cycle :
    print(num)
else :
    print('0')