백준 20040번: 사이클 게임 / C++
2023. 4. 3. 22:45ㆍ개인공부/코딩테스트
20040번: 사이클 게임
사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <iostream>
using namespace std;
int arr[500000]{};
int n, m;
int Find(int num)
{
if (arr[num] < 0)
return num;;
int index = Find(arr[num]);
arr[num] = index;
return index;
}
void Union(int x, int y)
{
x = Find(x);
y = Find(y);
if (x == y)
return;
if (arr[x] < arr[y]) {
arr[x] += arr[y];
arr[y] = x;
}
else {
arr[y] += arr[x];
arr[x] = y;
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
// 초기화
for (int i = 0; i < n; ++i)
arr[i] = -1;
bool IsCheck = false;
for (int i = 0; i < m; ++i){
int num1, num2; cin >> num1 >> num2;
if (!IsCheck&&Find(num1) == Find(num2) ) {
cout << i + 1;
IsCheck = true;
return 0;
}
Union(num1, num2);
}
if (!IsCheck)
cout << 0;
return 0;
}
|
cs |
'개인공부 > 코딩테스트' 카테고리의 다른 글
| 11758번 : CCW / C++ (0) | 2023.06.18 |
|---|---|
| 백준 16135번 : OBB(Oriented bounding box) / C++ (0) | 2023.06.15 |
| 백준 1717번: 집합의 표현 / C++ (0) | 2023.04.03 |
| 백준 1450: 냅색문제 / C++ (0) | 2023.04.03 |
| 백준 1806번 : 부분합 / C++ (0) | 2023.04.02 |