[알고리즘] 유니온파인드 & 사이클게임

유니온 파인드

• 해당 노드의 최상위 부모를 기록해놓는 방식
• 만약에 최상위 노드가 다르다면, 서로 다른 그래프임을 알 수 있다.
• 자세한 내용은 해당 링크 참고.

사이클 게임

구현 방식

• 이미 최상위 부모가 같은 노드들을 다시 연결 시도하면 사이클이 발생한다.

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int N, M;
	cin >> N >> M;
	vector<int> parent(N);

    // 초기에는 엣지들이 따로 연결 안되었으니,
    // 모든 노드의 부모 노드가 자기 자신을 가르킴
	for (int i = 0; i < N; i++)
	{
		parent[i] = i;
	}

	vector<pair<int, int>> edges(M);
	for (int i = 0; i < M; i++)
	{
		cin >> edges[i].first >> edges[i].second;
	}

	solution(parent, edges);

	return 0;
}

void solution(vector<int>& parent, vector<pair<int,int>>& edges)
{
	int result = 0;
	for (auto& edge : edges)
	{
        // 이미 최상위 부모가 같은 노드들을 다시 연결 시도하면
        // 사이클이 발생한다.
		if (findParent(parent, edge.first, edge.second))
		{
			cout << ++result;
			return;
		}
		else
		{
			unionParent(parent, edge.first, edge.second);
			result++;
		}
	}

	cout << 0;
}


int getParent(vector<int>& parent, int x)
{
	if (parent[x] == x)
		return x;
	else
		return getParent(parent, parent[x]);
}

// 두 부모를 합치는 함수
void unionParent(vector<int>& parent, int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a > b) parent[a] = b;
	else parent[b] = a;
}

// 같은 부모를 가지는지 확인
bool findParent(vector<int>& parent, int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);
	return a == b;
}