[python] 백준 20040 사이클 게임

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

20040번: 사이클 게임

 

문제 해결

• 1~m 번호까지 차례대로 원하는 두 점을 연결한다.(중복 불가)
• 어 때 몇 번째 번호에서 사이클이 만들어지는지 구하는 문제이다.
• 처음에는 하나의 선분이 그어질 때마다 사이클이 존재하는지 직접 돌려야되나 생각했다.
• 하지만 유니온 파인드(union find)를 이용하면 계산양을 줄이고 쉽게 사이클이 만들어지는지 확인할 수 있음을 알 수 있었다.
• 그림으로 이해하면 너무 쉽다.

CODE

import sys
input = sys.stdin.readline

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

def union(x,y,idx):
    global answer
    x = find(x)
    y = find(y)
    if x != y:
        parents[max(x,y)]= min(x,y)
    elif answer ==0:
        answer = idx
    
if __name__=='__main__':
    n, m = map(int, input().split())
    parents = [i for i in range(n)]
    answer =0
    for t in range(1,m+1):
        a, b = map(int, input().split())
        union(a,b,t)
    print(answer)