20040번: 사이클 게임 (acmicpc.net) 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 1. 사용한 알고리즘: 서로소 알고리즘(유니온 파인드) 2. 사이클 찾기: 여기서 빨간색 줄을 마지막으로 연결한다고 가정했을때, 왼쪽은 3번 키값의 value는3, 5번키값의 value는 3으로 같고, 오른쪽은 5번 키값의 value는3, 1번키값의 value는 1로 다르다. 이렇게 사이클은 새로운 edge를 추가할때 출발점의 부모와 도착점의 부모가 같으면 사이클이 발생했다고 판단한다. 3. 구현:

Union-Find(유니온 파인드)그래프 알고리즘 중 하나로 서로소(disjoint sets) 집합 자료구조이다. 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현하는데, 서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.1. union(합집합)연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.       - A와 B의 루트 노트 A', B'를 각각 찾는다.       - A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.)2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.17. Union-Find(..