BOJ 20040 | 사이클 게임

Union Find 기본 문제이다.

처음에는 노드를 연결할 때마다 사이클이 있는지 탐색하려고 했지만 N과 M의 범위를 보니 시간초과가 날 것 같아서 다른 방법을 고민했다.

그러다가 최소 스패닝 트리를 구현할 때 Union Find를 써서 Cycle이 형성되는지 체크했던 기억이 나서 분리 집합으로 구현했다.

기본 아이디어는 연결할 두 노드 x, y가 이미 연결되어 있으면 cycle이 형성된다고 판단하는 것이다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

class UnionFind{
private:
	vector<int> parent;
public:
	UnionFind(int n){
		parent.resize(n+1);
		for (int i = 0; i <= n; i++){ // parent[i] = i's parent
			parent[i] = i;
		}
	}
	int Find(int x){
		if (x == parent[x]) return x;
		return parent[x] = Find(parent[x]);
	}
	void Union(int x, int y){
		x = Find(x);
		y = Find(y);
		parent[y] = x;
	}
	vector<int> tree(){
		return parent;
	}
};



int main(){
	FASTIO;
	
	int N, M; cin >> N >> M;
	UnionFind S = UnionFind(N);
	//vector<Node> node;
	
	for (int i = 0; i < M; i++){
		int x, y; cin >> x >> y;
		if (S.Find(x) != S.Find(y)){
			S.Union(x, y);
		}
		else{ // cycle
			cout << i+1;
			return 0;
		}
	}
	
	
	cout << 0;
	
}