[PS] BOJ 20040 사이클게임

유니온 파인드 알고리즘 - 유니온 파인드에 대해 이 블로그를 참고했습니다.

간단하게 정리하자면, 노드를 합치는 Union 함수와 루트 노드를 찾는 Find 함수를 구현해 활용!

---

문제 링크

문제 요약

두 명의 플레이어(선이 홀수, 후가 짝수 차례)는 매 차례 마다, 기존의 선분과 겹치지 않도록(교차는 가능) 두 점을 선택해서 이를 연결한 선분을 긋는다.

처음으로 사이클을 완성하는 순간 게임이 종료된다.

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

몇 번째 차례에서 처음으로 사이클이 완성되는지 출력하는 문제

Input

• 첫 번째 줄 n, m
  • n: 점의 개수를 나타내는 정수 (3 ≤ n ≤ 500,000)
  • m: 진행된 사례의 수를 나타내는 정수 (3 ≤ m ≤ 1,000,000)
• m개의 줄
  • 각각 i번째 차례에 해당 플레이어가 선택한 두 점의 번호 (1 ≤ i ≤ m)

Output

• if m번째 차례까지 게임 진행
  • 사이클이 처음으로 만들어진 차례의 번호 출력
• if m번 차례 모두 처리한 이후에도 종료X
  • 0 출력

---

풀이 과정

1. 루트 노트를 찾는 find_parent() 구현
2. 노드를 합치는 union() 구현
3. 사이클이 발생하면(두 노드의 루트노드가 같으면) 해당 차례 출력
   • 사이클 안 생기면 두 노드 합치기

n, m = map(int, input().split())
parent = [i for i in range(n)] # list(range(n))

def find_parent(x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]
    
def union(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
for i in range(m):
    a, b = map(int, input().split())
    if find_parent(a) == find_parent(b): # 사이클
        print(i + 1)
        break
    union(a, b)
else:
    print(0)

Python3는 시간 초과가 떠서 PyPy3로 제출했다.