[백준 C++] 20040번: 사이클 게임

1. 문제

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

20040번: 사이클 게임

 

2. 알고리즘 분류

• 자료 구조
• 분리 집합

 

3. 소스 코드

Key Point)
1. 사이클 여부를 확인하는 문제는 Union-Find를 활용한다.
2. a와 b의 parent가 같으면, 사이클이다.

 

#include <iostream>

using namespace std;

int parent[500005];

int Find(int a)
{
	if (a == parent[a]) return a;
	else return parent[a] = Find(parent[a]);
}

bool Union(int a, int b)
{
	int pA = Find(a);
	int pB = Find(b);

	if (pA == pB) return true; // 사이클 발생
	else
	{
		parent[pB] = pA;
		return false;
	}
}

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

	for (int i = 0; i < 500005; i++)
		parent[i] = i;

	int n, m;
	int ans = 0;
	
	// 점의 개수(n)과 차례의 수(m) 입력
	cin >> n >> m;

	// 각 차례마다 두 점을 선택
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;

		// 사이클 여부 확인한 후, 사이클이면 ans에 값 할당
		if (Union(a, b))
		{
			ans = i;
			break;
		}
	}

	// 정답 출력
	cout << ans;

	return 0;
}

 

4. 유용한 문법 및 알고리즘

 1) Union-Find

• 특정 노드나 점을 그룹핑(Grouping) 할 때 사용한다.
• 해당 그래프가 사이클인지 확인할 때, Union-FInd를 활용한다.

 

int Find(int a)
{
	if (a == parent[a]) return a;
	else return parent[a] = Find(parent[a]);
}

bool Union(int a, int b)
{
	int pA = Find(a);
	int pB = Find(b);

	if (pA == pB) return true; // 사이클 발생
	else
	{
		parent[pB] = pA;
		return false;
	}
}