[BOJ] 20040 사이클 게임

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

1차 시도도 안 함

강의에서 문제 설명으로 Union-Find를 사용하면 된다고 해서 예전에 만들었던 Union-find 코드를 확인했는데 이걸로 어떻게 사이클을 탐지할지 고민을 했지만 떠오르지 않았다.

강의에서 알려준 Union-Find

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

def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)

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

조금 달라지긴 했는데 이전에 알려준 코드와 역할은 크게 다르지 않다. 부모의 부모를 찾아서 루트 노드를 찾고 둘이 비교해서 두 집합을 합치는 것인데, 강의를 듣다보니까 이해가 된 것은 입력된 점 두 개가 서로 다른 집합에 있다면 사이클이 생기지 않는데 둘 다 한 집합 안에 있다면 사이클이 생기는 것으로 판단할 수 있었다. 그래서 그냥 기존 union-find 코드에서 find만 밖에서 각각 한 번씩 해주는 방식으로 사이클을 찾을 수 있었다. 이걸 왜 생각못했지......