[백준] 20040번 사이클 게임

문제: 20040번: 사이클 게임

 

#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

vector<int> dots;
vector<int> sizes;

int find_set(int u) {
	if (dots[u] == u)
		return u;
	return dots[u] = find_set(dots[u]);
}

bool union_(int u, int v) {
	int ur = find_set(u);
	int uv = find_set(v);

	// 다른 집합에 있으면 연결해줘야함
	if (ur != uv) {
		if (sizes[ur] < sizes[uv]) swap(ur, uv);

		sizes[ur] += sizes[uv];
		dots[uv] = ur;
		
		return false;
	}
	// 이미 같은 집합에 있어?
	else if (ur == uv) {
		// 같은 집합에 있는데 또 연결하는건 사이클
		return true;
	}
}


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

	int n, m; // n: 점의 개수, m: 진행된 차례 수
	cin >> n >> m;
	int cnt = 1;

	dots = vector<int>(n);
	sizes = vector<int>(n, 1); // 1 로 초기화..
	for (int i = 0; i < n; i++)
		dots[i] = i;

	while (m-- > 0) {
		int a, b; // 연결한 두 점
		cin >> a >> b;

		// 두 점 연결
		if (union_(a, b)) {
			cout << cnt << "\n";
			break; // 만약 사이클 생성되면 빠져나가도록..
		}
		else {
			cnt++;
			continue;
		}
	}

	if (m == -1)
		cout << 0 << "\n"; // m 번의 차례 이후에도 종료되지 않았다면 0 출력


	return 0;
}

 

Disjoints Set 에 대해 알면 쉽게 해결할 수 있는 문제였다.

 

사이클 여부를 판단하는 방법은 입력으로 주어진 두 개의 점을 연결하려고 했을 때, 이미 같은 집합에 속한 애들이면 사이클인 것이다..

 

기본 Disjoints Set 구현 코드를 아주 조금만 변형하면 풀리는 문제였다. 복습하는 기분이라 괜찮았다.