并查集¶

export default class DisjointSetItem {
  constructor(value) {
    this.value = value;
    this.parent = null;
    this.children = {};
  }

  getKey() {
    return this.value;
  }

  getRoot() {
    if (this.parent === null) {
      return this;
    }

    return this.parent.getRoot();
  }

  getChildren() {
    return Object.values(this.children);
  }

   /**
   * 后代的总数
   *
   * @return {number}
   */
  getRank() {
    if (this.getChildren().length === 0) {
      return 0;
    }

    let rank = 0;
    this.getChildren().forEach(child => {
      rank += 1;
      rank += child.getRank();
    });

    return rank;
  }

  addChild(childItem) {
    this.children[childItem.getKey()] = childItem;
    childItem.parent = this;

    return this;
  }
}

import DisjointSetItem from './DisjointSetItem.js'

/**
 * 并查集
 * 是一种树型的数据结构，用于处理集合的合并及查询问题。
 * 
 * 并查集的思想是用一个数组表示了整片森林（parent），
 * 树的根节点唯一标识了一个集合，
 * 只要找到了某个元素的的树根，就能确定它在哪个集合里。
 * 
 * 合并(Union)：把两个不相交的集合合并为一个集合。
 * 查询(Find)：查询两个元素是否在同一个集合中。
 * */
export default class DisjointSet {
  constructor(keyCallback) {
    this.items = {};
  }

  /**
   * @param {*} itemValue
   * @return {DisjointSet}
   */
  makeSet(itemValue) {
    const disjointSetItem = new DisjointSetItem(itemValue);

    if (! this.items[disjointSetItem.getKey()]) {
      this.items[disjointSetItem.getKey()] = disjointSetItem;
    } 

   return this;
  }

   /**
   * Find set representing node Key.
   *
   * @param {*} itemValue
   * @return {(string|null)}
   */
  find(itemValue) {
    const templateDisjointItem = new DisjointSetItem(itemValue);
    const requiredDisjointItem = this.items[templateDisjointItem.getKey()];

    if (!requiredDisjointItem) {
      return null;
    }

    return requiredDisjointItem.getRoot().getKey();
  }

  /**
   * Union by rank.
   *
   * @param {*} valueA
   * @param {*} valueB
   * @return {DisjointSet}
   */
  union(valueA, valueB) {
    const rootKeyA = this.find(valueA);
    const rootKeyB = this.find(valueB);

    // 不在集合中
    if (!rootKeyA || !rootKeyB) {
      throw new Error('有元素不在集合中');
    }

    // 已同一集合中
    if (rootKeyA === rootKeyB) {
      return this;
    }

    const rootA = this.items[rootKeyA];
    const rootB = this.items[rootKeyB];

    // 树大者为根
    if (rootA.getRank() > rootB.getRank()) {
      rootA.addChild(rootB);
    } else {
      rootB.addChild(rootA);
    }

    return this;    
  }

  inSameSet(valueA, valueB) {
    const rootKeyA = this.find(valueA);
    const rootKeyB = this.find(valueB);

    if (!rootKeyA || !rootKeyB) {
      throw new Error('有元素不在集合中');
    }

    return rootKeyA === rootKeyB;
  }
}