여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘
- 여러 개의 노드가 모두 연결되어있지않고 각자 자기 자신만을 원소로 갖고 있을 때
- 만약 2와 1이 연결되어있을 때
부모를 합치는데 연결된 노드 중에서 더 작은 값을 부모 노드로 바꿔준다.
- union과정(합치는 과정)
2-1. 또 2와 3이 연결되었을때
부모노드를 비교해 더 작은 수로 바꿔준다.(3의부모노드를 3->2)
그래프를 봤을때 3과 1은 연결되어있는데 부모노드가 다르다.
이를 확인하기위해 재귀함수를 사용해서 결과적으로 3의 최종적인 부모는 1이라는 것을 확인한다.
- find 알고리즘 - 두 개의 노드를 비교해서 같은 집합인지
union-find의 핵심
-> 특정한 노드들을 선택했을때 그 노드가 같은 그래프에 속해있는지
너네 지금 같은 부모를 가지고 있니?
-> find 알고리즘
