[백준] 20040번 - 사이클 게임 (C++) 문제 및 풀이

문제) 백준 - 분리 집합 - 사이클 게임

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

20040번: 사이클 게임

 

분리 집합을 이용하여 쉽게 풀 수 있는 문제. 선분을 그리면 같은 집합으로 merge하고 parent가 같을 경우 사이클이 있는 것으로 간주한다.

 

 

C++ 소스 코드)

	#include <bits/stdc++.h>
	#define endl "\n"
	#define MAX 5000001
	using namespace std;
	typedef pair<int, int> p;
	struct DisjointSet {
	vector<int> parent, rank;
	DisjointSet(int n) :parent(n), rank(n + 1) {
	for (int i = 0l; i < n; ++i)
	parent[i] = i;
	}
	int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
	}
	void merge(int u, int v) {
	u = find(u); v = find(v);
	if (u == v) return;
	if (rank[u] > rank[v]) swap(u, v);
	parent[u] = v;
	if (rank[u] == rank[v]) ++rank[v];
	}
	bool isSame(int b, int c) {
	if (find(b) == find(c))
	return true;
	else return false;
	}
	};
	signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	DisjointSet ds(n + 1);
	int ans = 0;
	for (int i = 0; i < m; ++i) {
	int a, b; cin >> a >> b;
	if (ds.isSame(a, b)) {
	ans = i + 1;
	break;
	}
	else {
	ds.merge(a, b);
	}
	}
	cout << ans << endl;
	}

view raw 20040.cpp hosted with ❤ by GitHub

 

ps. 사이클에 꽂혀서 dfs만 주구장창 생각했다...