[백준 문제풀이] 백준 20040 c++ 사이클 게임

유니온 파인드를 활용해서 풀 수 있는 문제

 

---

유니온 파인드란?

- 여러 개의 부분집합을 루트를 기준으로 병합, 각 원소의 루트 찾기를 할 수 있는 자료구조

 

초기화: 각 노드는 자신의 번호로 초기화  list[i] = i;

find 과정(루트 찾기): list[a] = b 로, 루트와 연결된 노드의 값을 이용하여 루트 값을 반환 하도록 하는 함수

 

union 과정(병합): find 함수를 이용하여 두 수의 루트 값을 찾고, 그 값이 같다면 같은 부분집합이며 다르다면 병합 할 수 있도록 하는 함수

 

#include <iostream>
#include <algorithm>

int list[500001] = {};
int check = 0;

void init(int n) {
	for (int i{ 0 }; i <= n; i++) list[i] = i;
}

int find(int n) {
	if (list[n] == n) return n;
	else return find(list[n]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) {
		return;
	}
	else list[b] = a;
}

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n, m;
	std::cin >> n >> m;

	init(n);

	int a, b;
	int ans = 0;
	for (int i{ 0 }; i < m; i++) {
		std::cin >> a >> b;
		if (ans) continue;
		else if (find(a) == find(b)) {
			ans = i + 1;
		}
		else merge(a, b);
	}

	if (!ans) std::cout << "0\n";
	else std::cout << ans << "\n";
}