Union-Find 알고리즘

Union-Find 알고리즘

- 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서 현재 이 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

Union-Find 동작 과정

처리할 연산 : Union(1,2), Union(2,3),Union(5,6)
1. n개의 부모노드를 초기화 해준다

2. Union(1,2) : 노드1의 부모와 노드2의 부모를 찾고 둘의 부모가 다르면 부모를 같에 만들어준다
- 노드2번의 부모에 노드1의 부모 1을 넣어준다
3.Union(2,3)
- 노드3번의 부모에 노드2의 부모 1을 넣어준다
4.Union(5,6)
- 노드6번의 부모에 노드5의 부모 5를 넣어준다
결과 : 노드1,2,3은 같은 집합, 노드5,6이 같은 집합, 노드4는 단독적인 집합에 존재하게된다.

Union-Find 구현 방법

• Set (초기화) : n개의 부모노드가 각각의 집합에 포함되게 초기화
• Union (합치기) : 두 원소의 각각의 집합을 같은 집합으로 합친다
• Find (찾기) : 원소 a가 들어오면 그 원소가 어느 집합에 포함되어 있는지 찾아서 반환한다

[구현]

#include <stdio.h>
int parent[1001];
int Find(int v)
{
	if(parent[v] == v) return v; // 노드의 부모가 v값과 같으면 부모가 같기에 부모를 리턴
	
	return parent[v] = Find(parent[v]); //노드의 부모가 같을 때까지 반복
}
void Union(int x, int y) // 연결시키기 or 연결됬는지 확인
{
	x = Find(x);
	y = Find(y);
	
	if(x != y) // x,y가 같다면 부모가 같기 때문에 다르면 저장해줌
		parent[x] = y; 
}
void Set(int n){ // parent 배열 초기화
	for(int i = 1; i <= n; i++){
		parent[i] = i;
	}
}
int main(void) {
   int n ,m, uf1,uf2;
   int f1,f2;
   scanf("%d %d",&n,&m);
		Set(n);
   for(int i = 1; i <= m; i++){
       scanf("%d %d",&uf1,&uf2);
				Union(uf1,uf2);
   }
   scanf("%d %d",&f1,&f2);
   printf("%s",(Find(f1) == Find(f2)) ? "YES":"NO" ); // 부모가 같다면 YES 다르면 NO를 출력
   return 0;
}