并查集的实现

用js实现一个并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class UFS {
  constructor() {
    this.set = [];
  }

  //初始化节点
  makeSet(x) {
    this.set[x] = {
      parent: x,
      rank: 0,
    };
  }

  //找出x的根节点
  find(x) {
    const node = this.set[x];
    if (!node) {
      return -1; //error
    } else if (node.parent == x) {
      return x;
    } else {
      return this.find(node.parent);
    }
  }

  //判断x和y是否在同一个集合中
  connected(x, y) {
    return this.find(x) === this.find(y);
  }

  //合并两个集合
  union(x, y) {
    if (this.connected(x, y)) {
      return true;
    }
    const xRoot = this.set[this.find(x)];
    const yRoot = this.set[this.find(y)];
    if (!xRoot || !yRoot) {
      //error
      return false;
    }

    if (xRoot.rank < yRoot.rank) {
      //往rank大的元素挂载，这样不增加rank
      xRoot.parent = y;
    } else if (xRoot.rank > yRoot.rank) {
      yRoot.parent = x;
    } else {
      xRoot.parent = y;
      yRoot.rank += 1;
    }

    return true;
  }
}