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

www.acmicpc.net/problem/20040

20040번: 사이클 게임

유니온 파인드를 이용해 해당 그래프에서 몇 번째에 사이클이 생기는 지 구하는 문제입니다. (없으면 0)

 

유니온 파인드 알고리즘은 두 노드를 연결시킬 때, 같은 집합(연결되었는지)인지 아닌지 판별하는 알고리즘입니다. 각 노드의 부모 노드를 찾아 부모 노드가 일치하면 연결되어있는 노드이고, 아니면 부모 노드를 연결 시켜주면 됩니다.

 

과정은 다음과 같습니다. 

1. 처음 각 노드이 부모 노드를 자기 자신으로 한다.

2. find : 부모를 찾는다. 해당 노드와 parent 배열의 값이 일치하면 리턴, 아니면 부모노드를 파라미터로 받아 다시 찾는다. 이를 반복한다. (재귀)

3. union : x, y 노드를 연결시킨다고 하자. 각각의 부모 노드를 찾는다. 일치하는 경우, 이미 연결되어있는 경우이고, 아니면 부모 노드를 연결시킨다. (해당 문제에서는 무향 그래프에서 사이클 유무를 판별하는 것이므로, x, y의 부모가 같은 경우, x, y가 연결되면 사이클이 발생한다.)

 

코드는 다음과 같습니다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

int n, m;
int* parent;
int result;

// 유니온 파인드. 처음에 각 노드의 부모를 자기 자신으로
void init()
{
	cin >> n >> m;
	parent = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
		parent[i] = i;
}

void end()
{
	cout << result;
	free(parent);
}

// 노드 x의 부모 노드를 찾는다.
int find_parent(int x)
{
	if (x == parent[x])
		return x;	
	else
		return find_parent(parent[x]);
}

// 노드 x, y가 연결된다 가정. 사이클 생기면 break
// 무향 그래프에서 사이클은 x, y의 부모 노드가 같은 경우 발생
// 사이클 안 생기고 연결되면 y의 부모가 x가 된다.
void union_and_result()
{
	int x, y;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		x = find_parent(x);
		y = find_parent(y);

		if (x == y) {
			result = i;
			break;
		}
		parent[y] = x;
	}
}

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

	init();
	union_and_result();
	end();
}