[BOJ] 사이클 게임

---

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
parent = [i for i in range(n)]
def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x])
    return parent[x]

def union_parent(a, b):
    a = get_parent(a)
    b = get_parent(b)

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

def is_cycle(a, b):
    return get_parent(a) == get_parent(b)

for i in range(m):
    a, b = map(int, input().split())
    if not is_cycle(a, b):
        union_parent(a, b)
    else:
        print(i+1)
        sys.exit()

print(0)

결과

풀이 방법

• Union-Find 알고리즘으로 사이클 여부를 판단하는 문제이다.
• 두 점을 연결하기 전에 각각의 parent를 확인하여 사이클인지 우선 확인하고, 사이클이 아니라면 union 연산으로 두 점을 연결한다.
• union 연산 시 부모가 작은 쪽이 큰 쪽의 부모가 된다.
• 연결 전에 현재 두 점을 연결하면 사이클이 형성되는 경우 차례를 출력하고 종료하도록 작성했다.

---