유니온 파인드 정리 C++

유니온 파인드 알고리즘은 무향 그래프에서 disjoint set을 union 하는 과정입니다. 

(유향 그래프의 경우, SCC에서 사용하는 타잔, 코사라주 등 이용)

 

각 그래프 노드의 부모 노드를 찾고, find 하는 과정을 반복합니다.

이 때 부모 노드는 단순히 바로 연결된 노드가 아닌, 최상위로 찾을 수 있는 부모를 의미합니다. 

 

따라서 사이클이 발생하는 경우는 두 노드의 부모 노드가 동일한 경우입니다. 

예를 들어, 1-2 / 2-3 / 2-4/ 3-4 와 같은 연결이 주어진다면, 3-4의 입력 때 사이클이 발생합니다. 

(부모 기준 : 작은 값이 부모)

 

코드는 다음과 같습니다.

 

#include <iostream>

using namespace std;

int find_parent(int node, int parent[])
{
	if(node == parent[node])
		return node;
	parent[node] = find_parent(parent[node], parent);
	return parent[node];	
} 

void union_nodes(int node1, int node2, int parent[])
{
	// 작은 값이 부모 노드 되도록
	int parent1 = find_parent(node1, parent);
	int parent2 = find_parent(node2, parent);
	
	// 부모 같은 경우 : cycle 발생 
	if(parent1 == parent2) {
		cout << "cycle!!!\n";
	}
	
	else if(parent1 < parent2)
		parent[parent2] = parent1;
	else
		parent[parent1] = parent2;
		
	cout << "node1 : " << node1 << " parent1 : " << parent1 << "\n";
	cout << "node2 : " << node2 << " parent2 : " << parent2 << "\n";
	
	return;
}

int main()
{
	// 작은 값이 부모 되도록 union find 
	
	// 입력
	// 1-2
	// 2-3
	// 2-4
	// 3-4 => cycle 발생 
	
	 // 각 노드의 부모 노드 처음에는 자기 자신 
	 int parent[5] = {0,1,2,3,4};
	 
	 union_nodes(1,2,parent);
	 union_nodes(2,3,parent);
	 union_nodes(2,4,parent);
	 union_nodes(3,4,parent); 
}