유니온 파인드(union find)

유니온 파인드

두 노드가 같은 그래프에 있는지 찾는 방법

그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set

1. Find -노드 x 가 어느 집합에 포함되어 있는지 찾는 연산
2. Union-노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산

 

 

parent[i]는 i의 부모가 무엇인지 나타내는 것,

parent[i] =i 는 i가 루트 노드임을 나타냄(부모가 본인이므로)

 

 

find함수 구현

int find(int x){
  if (x==parent[x]){
    return x;
  }
  else {
    return find[parent[x]];
  }
}

루트를 찾아 반환  하지만 이 함수의 문제점은 한쪽방향으로 치우칠 수 있다.(트리의 장점 소실)

이를 고치기 위해 오른쪽노드를 모두 루트노드에 연결하게 구현

int find(int x){
  if (x==parent[x]){
    return x;
  }
  else{
    int y = find(parent[x]);
    parent[x] = y;
    return y;
  }
}

유니온 함수 구현

union(x,y)- y의 parent를 x로 삼는다

ex)union(1,2) 라는 함수는 2의 노드가 1의 노드 자식으로 붙게 됨을 의미

void union(int x,int y){
  x = find(x);
  y = find(y);
  parent[y] = x;
}