Union-Find

https://baebalja.tistory.com/317

[백준 1197번 / C++ / 크루스칼] 최소 스패닝 트리

https://m.blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)

#include <iostream>
using namespace std;

// 재귀로 구성
// 최종 부모 노드를를 찾기 위한 작업 
int getParent(int parent[], int x){
	if(parent[x] == x) return x; // 최종 부모에 도달했을때(재귀종료조건) 
	return parent[x] = getParent(parent, parent[x]); 
}

void unionParent(int parent[], int a, int b){
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a<b) parent[b] = a;
	else parent[a] = b;
	
} 

int findParent(int parent[], int a, int b){
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a==b) return 1; // 부모가 같으면연결되어 있음 
	return 0;           // 부모가 다르므로 연결되어 있지 않음 
}

int main(){
	int parent[11];
	for (int i=1;i<=10;i++){
		parent[i] = i;  // 자기 자신으로 초기화 
	}
	
	unionParent(parent, 1, 2);
	unionParent(parent, 2, 3);
	unionParent(parent, 3, 4);
	unionParent(parent, 5, 6);
	unionParent(parent, 6, 7);
	unionParent(parent, 7, 8);
	cout << "1과 4가 연결되어있습니까? " << findParent(parent,1,4) << "\n";  // yes
	cout << "1과 5가 연결되어있습니까? " << findParent(parent,1,5);
}