풀이
n개의 점에 대해 주어지는 m개의 선분이 사이클을 이루는지 확인하는 문제다.
쉽게 두 원소 x, y에 대해 union할 때 대표 원소가 동일하다면, 선형 구조상 동일한 집합에 속한 원소들이고 한 번 더 연결하려 시도했기 때문에 사이클을 형성할 것이다.
만약 union이 모두 정상적으로 이루어졌다면, 동일한 집합에 속한 원소들끼리 union이 이루어지지 않았기에 사이클은 생길 수 없다.
사이클이 생기지 않은 경우에는 0을 출력하면 된다.
소스코드
출처
20040번: 사이클 게임
사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 21633] Bank Transfer [Python] (0) | 2023.07.04 |
|---|---|
| [백준 10775] 공항 [Java] (0) | 2023.07.04 |
| [백준 4375] 1 [Java] (0) | 2023.06.29 |
| [백준 4195] 친구 네트워크 [Java] (0) | 2023.06.29 |
| [백준 1976] 여행 가자 [Java] (0) | 2023.06.29 |