[알고리즘/파이썬] 백준 20040 - 사이클 게임

문제

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

20040번: 사이클 게임

 

풀이

유니온 파인드를 사용해서 풀었다.

 

union - 두 노드 중 작은 노드를 큰 노드의 부모 노드로 지정하는 함수

find - 노드의 루트 노드를 찾는 함수

 

부모 노드가 똑같은 두 노드 연결되면 사이클이 생긴것으로 판단하고 해당 과정을 result에 담는다.

 

코드

import sys
input = sys.stdin.readline
n, m = map(int,input().split())

parents = [i for i in range(n)]

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

def union(a,b):
    a = find(a)
    b = find(b)

    if a<b:
        parents[b] = a
    else:
        parents[a] = b

def is_same_parent(a,b):
    if find(a)==find(b):
        return True
    else:
        return False
    
result = 0
for i in range(m):
    a,b = map(int,input().split())
    if result != 0: continue

    if is_same_parent(a,b):
        result = i+1
    else:
        union(a,b)

print(result)