[BOJ]20040번: 사이클 게임

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

---

유니온/파인드 문제입니다.

 

진행된 차례 m의 상한이 100만이므로 한 차례마다 사이클 탐색에 O(M)이 소모되면 O(M^2)으로 시간초과가 됩니다.

 

그러므로 현재 차례에서 사이클을 탐색하는데 시간을 줄여야 시간 초과가 나지 않습니다.

 

사이클 판별 방법

 

1. 매 두 점이 들어올 때 마다 두 점을 union 연산으로 같은 컴포넌트로 연결시켜줍니다.

2. 특정 차례에서 들어온 두 점이 이미 같은 컴포넌트에 있다면, 이 둘을 연결시키면 싸이클이 만들어집니다.

 

싸이클 판별인 find 연산에 O(logM)이 걸리므로 시간 복잡도는 O(MlogM)입니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ20040.java