알고리즘 스터디 - 백준 20040번 : 사이클 게임

문제 해석

• 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임
• 선 플레이어/홀수, 후 플레이어/짝수

사이클 C : 플레이어가 그린 선분들의 부분집합

• C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분들 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

점의 개수 n과 m 번째 차례까지의 게임 진행 상황에서 언제 처음으로 사이클이 완성된 것인지 출력

• 여기서 중요한 단어는 '사이클'이다. 사이클이라는 것은 트리 속에서 루프 노드가 서로 다른 것이 아니고 루프 노드가 서로 같을 때 사이클이 발생한 것이라고 말할 수 있다.
• 따라서 유니온 파인드 함수를 통하여 루프 노드가 같아지는 시점을 찾아 반환해주면 된다.

알고리즘 코드

import sys

input = sys.stdin.readline

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

# 부모노드 생성
parent = [i for i in range(n+1)]

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

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

    if a == b:
        return True
    else:
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
    return False

answer = 0

for i in range(m):
    a, b = map(int, input().split())
    # 최초 사이클 생성이기 때문에 answer가 갱신되기 전에 해야하고 
    # 또한, union을 했을 때에도 True가 나오는 지점을 알 수 있다.
    if union(parent, a, b) and answer == 0:
        answer = i + 1

print(answer)