[백준/BOJ] 백준 20040번 : 사이클 게임

www.acmicpc.net/problem/20040

20040번: 사이클 게임

유니온 파인드를 이용하여 처음으로 사이클이 만들어졌을 때를 찾았다. ranks를 이용해 트리의 깊이를 작게 만들어서 유니온 파인드 시간을 줄였다.  

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
vector<int> parent(500000);
vector<int> ranks(500000);

void Pre()
{
	for (int i = 0; i < n; i++)
	{
		parent[i] = i;
		ranks[i] = 1;
	}
}

//유니온 파인드의 파인드
int Find(int u)
{
	if (u == parent[u])
		return u;

	return parent[u] = Find(parent[u]);
}

//유니온 파인드의 유니온
bool Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return false;

	//트리의 깊이를 작게하기 위해 ranks[]를 사용
	//ranks[]가 큰쪽으로 합친다
	if (ranks[u] > ranks[v])
		parent[v] = u;

	else
	{
		parent[u] = v;

		//ranks[]가 같다면 v쪽으로 합쳤으므로 v쪽의 ranks[]증가
		if (ranks[u] == ranks[v])
			ranks[v]++;
	}

	return true;
}

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

	int u, v;
	int result = 0;
	bool find_result = false; //처음으로 사이클이 만들어졌을때를 찾았는지 확인하는것

	cin >> n >> m;

	Pre();

	for (int i = 1; i <= m; i++)
	{
		cin >> u >> v;

		//처음으로 사이클이 만들어졌을때를 찾았을때
		if (!find_result && !Merge(u, v))
		{
			result = i;
			find_result = true;
		}
	}

	cout << result;

	return 0;
}