Union Find: Disjoint Set

Tree, MST (Kruskal)

Disjoint-set: 상호 배타적인 부분 집합 => 공통 원소가 없는 집합들을 표현하기 위해 만들어 졌다

공통 원소가 없는, 즉 "상호 배타적" 인 부분 집합 들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

The Union-Find algorithm is typically used for problems related to disjoint sets, such as determining if two nodes belong to the same set or not, and merging two sets into one. It's a very efficient algorithm for these types of problems.

Structure

class UnionFind {
    tracking: number[]; // 
    weights: number[]; // how tall the tree is 
    constructor();
    createSet(v: number);
    find(v: number): number; // return root of v
    union(v1, v2): void; // 
}

Implementation

// Do not edit the class below except for
// the constructor and the createSet, find,
// and union methods. Feel free to add new
// properties and methods to the class.
class UnionFind {
  constructor() {
    // Write your code here.
    this.parents = [];
    this.weights = [];
  }

  createSet(value) {
    this.parents[value] = value;
    this.weights[value] = 1;
  }

  find(value) {
    if (this.parents[value] === undefined) return null;
    if (this.parents[value] === value) return value;

    return this.parents[value] = this.find(this.parents[value]);
  }

  union(valueOne, valueTwo) {
    const root1 = this.find(valueOne);
    const root2 = this.find(valueTwo);

    if (root1 === null || root2 === null) return;
    if (root1 === root2) return;

    const weight1 = this.weights[root1];
    const weight2 = this.weights[root2];

    if (weight1 === weight2) {
      this.parents[root1] = root2;
      this.weights[root1] += 1;
    } else if (weight1 > weight2) {
      this.parents[root2] = root1;
      this.weights[root2] += 1;
    } else {
      this.parents[root1] = root2;
      this.weights[root1] += 1;
    }
    
    return;
  }
}

// Do not edit the line below.
exports.UnionFind = UnionFind;

reference

AlgoExpert | Ace the Coding Interviews

[알고리즘] 크루스칼(Kruskal)과 프림(Prim)옹벨 일기

[자료구조]Union-Find: Disjoint Set의 표현멍멍멍