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

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

20040번: 사이클 게임

#include <iostream>
using namespace std;
int N, M;
int parent[1000001];

int find(int a)
{
	if (parent[a] == a)
		return a;

	return parent[a]=find(parent[a]);
}

void Union(int a, int b)
{
	a = find(parent[a]);
	b = find(parent[b]);

	if (a != b)
	{
		if (a >= b)
			parent[a] = b;
		else
			parent[b] = a;
	}
}

bool Parent(int a, int b)
{
	a = find(a);
	b = find(b);
	if (a != b)
		return false;
	return true;
}
int main(void)
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		parent[i] = i;

	int a, b;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;	
		if (Parent(a, b))
		{
			cout << i + 1;
			return 0;
		}
		Union(a, b);
	}
	cout << "0";
}

 

Union-Find 알고리즘으로 풀어지는 문제입니다.

연결하기 전 두 노드의 부모가 같은지 확인합니다.

만약 같은 부모라면 연결하면 사이클이 생기겠지요.

부모가 다르다면 그냥 연결해줍니다.