[백준] 20040번 - 사이클 게임 (파이썬)

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

# 사이클 게임
N, T = map(int, input().split())
parent = [i for i in range(N)]


def find_parent(x):
    if x != parent[x]:
        x = find_parent(parent[x])
    return parent[x]


def union_parent(x, y):
    x = find_parent(x)
    y = find_parent(y)
    if x < y:
        parent[y] = x
        return False
    elif x > y:
        parent[x] = y
        return False
    else:
        return True


for i in range(1, T+1):
    x, y = map(int, input().split())
    if union_parent(find_parent(x), find_parent(y)):
        print(i)
        break
    elif i == T:
        print(0)

 

Union-Find
1. parent 리스트 정의 (자기 자신으로 초기화)
2. 입력을 받으면서
    - find_parent : 자신의 값을 최상의 부모의 값으로 초기화
    - union_parent : 작은 노드의 값으로 두 노드의 부모를 일치시켜준다. + 부모가 같다면 사이클 발생
    - union_parent가 True : 사이클 발생, 현재 회차(i)를 출력, break
    - 마지막 입력까지도 사이클 발생X : print(0)