[알고리즘] Union-Find

// 그래프 관련 처리
// 대표적인 그래프 관련 알고리즘 Union-Find(합집합 찾기)

// 부모노드를 찾는 함수
function getParent(parentArr, x){
  if(parentArr[x] === x){
    return x;
  }
  parentArr[x] = getParent(parentArr, parentArr[x]);
  return parentArr[x];
}

// 두 부모노드를 합치는 함수
function unionParent(parentArr, a, b){
  a = getParent(parentArr, a);
  b = getParent(parentArr, b);
  if(a < b) parentArr[b] = a;
  else parentArr[a] = b; // 항상 더 작은 값으로
}

// 같은 부모를 가지는지 확인
function findParent(parentArr, a, b){
  a = getParent(parentArr, a);
  b = getParent(parentArr, b);
  
  if(a == b) return 1;
  return 0;
}

const parentArr = [];
for(let i = 0; i <= 10; i++){
  parentArr.push(i);
}

unionParent(parentArr, 1, 2);
unionParent(parentArr, 2, 3);
unionParent(parentArr, 3, 4);
unionParent(parentArr, 5, 6);
unionParent(parentArr, 6, 7);
unionParent(parentArr, 7, 8);

parentArr;

console.log("1, 5 연결?", findParent(parentArr, 1, 5))

unionParent(parentArr, 1, 5)
console.log("1, 5 연결?", findParent(parentArr, 1, 5))