[C++] 백준 20040번: 사이클 게임

https://www.acmicpc.net/problem/20040

20040번: 사이클 게임

중요풀이

union-find 알고리즘을 활용하여 풀이를 진행한 대표적인 문제입니다.

union-find 알고리즘을 적용한다면 무난하게 풀어지는 문제입니다.

 

소스코드

#include <iostream>

using namespace std;

int parent[500001];

int find(int index) {
	if (parent[index] == index)return index;
	return parent[index] = find(parent[index]);
}

bool uni(int a, int b) {
	a = find(a);
	b = find(b);

	if (parent[a] == parent[b]) {
		return true;
	}
	if (a < b)
		parent[b] = a;
	else
		parent[a] = b;
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, a, b, answer = 0;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		parent[i] = i;
	bool check = true;//첫번째 사이클 턴을 출력하기 위함
	for (int i = 1; i <= m; i++) {
		cin >> a >> b;
		if (uni(a, b) == true && check ==true) {
			answer = i;
			check = false;
		}
	}

	cout << answer;

	return 0;
}