문제
백준 20040 사이클 게임 https://www.acmicpc.net/problem/20040
20040번: 사이클 게임
사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한
www.acmicpc.net
코드
#include<iostream>
using namespace std;
int n, m;
bool cycle = false;
int parent[500001];
int findUnion(int x) {
if (parent[x] == x) return x;
return parent[x] = findUnion(parent[x]);
}
void makeUnion(int x, int y) {
int px = findUnion(x);
int py = findUnion(y);
(px < py) ? parent[py] = px : parent[px] = py;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) parent[i] = i;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
if (findUnion(a)==findUnion(b)) {
cout << i;
return 0;
}
makeUnion(a, b);
}
cout << 0;
}풀이방법
유니온 파인드 알고리즘을 이용한다. 새로 연결되는 서로 다른 두 점의 parent가 같다면 사이클이 만들어진다. 따라서 for문을 돌리면서 union을 만들고, 사이클이 형성되는 경우 해당 반복횟수를 출력하고, for문이 끝날때까지 사이클이 만들어지지 않는다면 0을 출력한다.
고민과정
사이클이 생기는 조건을 떠올리기가 어려웠다..