유니온 파인드 알고리즘 - 유니온 파인드에 대해 이 블로그를 참고했습니다.
간단하게 정리하자면, 노드를 합치는 Union 함수와 루트 노드를 찾는 Find 함수를 구현해 활용!
두 명의 플레이어(선이 홀수, 후가 짝수 차례)는 매 차례 마다, 기존의 선분과 겹치지 않도록(교차는 가능) 두 점을 선택해서 이를 연결한 선분을 긋는다.
처음으로 사이클을 완성하는 순간 게임이 종료된다.
몇 번째 차례에서 처음으로 사이클이 완성되는지 출력하는 문제
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로 제출했다.