(백준/c++)20040번 - 사이클 게임

(백준/c++)20040번 - 사이클 게임📃 coding test/◽ 백준2022. 2. 15. 17:08@DoctorSunAhna

Table of Contents

728x90

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. 구현:

728x90

저작자표시 비영리 동일조건

'📃 coding test > ◽ 백준' 카테고리의 다른 글

(백준/c++) 17472번 - 다리만들기 (0)	2022.05.25
(백준/c++) 1976번 - 여행 가자 (0)	2022.02.15
(백준/c++)1780번 - 종이의 개수 (0)	2022.01.18
(백준/c++) 5430번 - AC (0)	2022.01.17
(백준/c++) 11054번 - 가장 긴 바이토닉 부분수열 (0)	2021.08.18

@DoctorSunAhna :: 핑크코냥

안 하는 것 보다 낫겠지

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

'📃 coding test > ◽ 백준' 카테고리의 다른 글

티스토리툴바