백준 20040번 사이클 게임 C++

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

 

유니온 파인드를 이용해서 두 점이 이미 같은 집합이라면 두 점을 이었을 때 사이클이 생긴다는 것을 이용해서 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

vector<int> parent;
vector<int> height;

int GetParent(int n) {
	if (n == parent[n])
		return n;
	return parent[n] = GetParent(parent[n]);
}

void Merge(int u, int v) {
	u = GetParent(u);
	v = GetParent(v);

	if (u == v)
		return;

	if (height[u] > height[v])
		::swap(u, v);

	parent[u] = v;

	if (height[u] == height[v])
		height[v]++;
}

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

	int ans = 0;
	int n, m;
	cin >> n >> m;
	parent = vector<int>(n);
	height = vector<int>(n, 1);
	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}
	bool isCycle = false;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		if (isCycle)
			continue;
		if (GetParent(u) == GetParent(v)) {
			isCycle = true;
			ans = i;
			continue;
		}
		Merge(u, v);
	}
	cout << ans;
}