概念

类似高中学过的集合的概念，一个元素对应唯一的集合；并查集通常包含两种操作，寻找元素的唯一集合和合并两个不相交集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
CONNECTED-COMPONENT(G)
    for each vertex v in G.V 
        MAKE-SET(v)
    for each edge(u,v) in G.E
        if FIND-SET(u) != FIND-SET(v)
            UNION(u,v)

SAME-COMPONENT(u,v)
    if FIND-SET(u) == FIND-SET(v)
        return true
    else
        return false
        
UNION(u,v)
    x=FIND-SET(u)
    y=FIND-SET(v)
    x.p=y

优化

但是这样顺序查找集复杂度为O(V)，可以使用按秩合并和路径压缩两种方法来降低复杂度。路径压缩指将所有的结点都指向根，尽可能快的到达集合里的根节点；按秩合并是指在合并时从低秩向高秩合并，尽量时子节点直接指向根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//路径压缩
FIND-SET(u)
    if u!=u.p
        u.p=FIND-SET(u.p)
    return u.p
//按秩合并
UNION(u,v)
    x=FIND-SET(u)
    y=FIND-SET(v)
    if x.rank<y.rank
        x.p=y
    else y.p=x
        if x.rank==y.rank
        x.rank=x.rank+1

LeetCode之并查集

261.Graph Valid Tree
输入n与结点对数组（每个对表示一条无向边），判断该图是否是有效树。

树的概念：树是一种任意两个结点都由一条无向边连接的图，也就是不存在环。这道题其实用DFS或者BFS也是可以解的。不过用并查集更易理解。若检测出某条边两个结点在同一个集中，即存在环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var isValidTree = function (n, edges) {
  var parent = new Array(n).fill(0);
  parent.forEach(function (item, index, array) {
    array[index] = index;
  });
  //find parent
  for (var i = 0; i < edges.length; i++) {
    console.log("parent,prerequisites[i][0]:", parent, edges[i][0]);
    var x = root(parent, edges[i][0]);
    var y = root(parent, edges[i][1]);
    if (x == y) return false;
    //union
    parent[x] = y;
  }
  return edges.length == n - 1;
};

var root = function (parent, i) {
  while (parent[i] != i) {
    i = parent[i];
  }
  return i;
};

305.Number of Islands II
对每次加入一块陆地的操作，计算该次操作后有几块岛。

还是并查集的问题，对每次加入后的1附近四个方向的4条边进行查找与合并。最后计算有多少个不相交集。需要将二维转化为一维的集合。

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
var Island = function (grid) {
  this.grid = grid;
  this.islands = [];
  this.parent = new Array(grid.length * grid[0].length).fill(-1);
  this.rank = new Array(grid.length * grid[0].length).fill(0);
};

Island.prototype = {
  addLand: function (i, j) {
    if (!(i > -1 && j > -1 && i < grid.length && j < grid[0].length)) {
      return this.islands;
    }
    this.grid[i][j] = 1;
    this.parent[i * this.grid[0].length + j] = i * this.grid[0].length + j;
    var dir = [[0, -1], [1, 0], [0, 1], [-1, 0]];
    for (var k = 0; k < dir.length; k++) {
      if (i + dir[k][0] > -1 && j + dir[k][1] > -1 && i + dir[k][0] < grid.length && j + dir[k][1] < grid[0].length &&
        this.grid[i + dir[k][0]][j + dir[k][1]] == 1) {
        var x = this.find(i * this.grid[0].length + j);
        var y = this.find((i + dir[k][0]) * this.grid[0].length + j + dir[k][1]);
        if (x != y) {
          this.union(x, y);
        }
      }
    }
    // console.log("this.parent:",this.parent);
    var map = {}, res = 0;
    for (k = 0; k < this.parent.length; k++) {
      // console.log("this.find(this.parent[k]:",this.find(this.parent[k]));
      if (this.find(this.parent[k]) != -1) map[this.find(this.parent[k])] = 1;
    }
    for (var val in map) res++;
    this.islands.push(res);
    return this.islands;
  },
  find: function (index) {
    while (index != -1 && this.parent[index] != -1 && index != this.parent[index]) {
      index = this.parent[index];
    }
    return index == -1 ? -1 : this.parent[index];
  },
  union: function (m, n) {
    if (this.rank[m] < this.rank[n]) {
      this.parent[m] = n;
    } else {
      this.parent[n] = m;
      if (this.rank[n] == this.rank[m]) this.rank[m]++;
    }
  }
};

323.Number of Connected Components in an Undirected Graph
计算不相交集

同样可以用DFS和BFS来解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var findComponentsUF = function (n, edges) {
  var parent = [], res = 0;
  var map = {};
  for (var i = 0; i < n; i++) {
    parent.push(i);
  }
  for (i = 0; i < edges.length; i++) {
    var x = edges[i][0], y = edges[i][1];
    parent[root(parent, x)] = root(parent, y);
  }
  for (i = 0; i < n; i++) {
    map[root(parent, i)] = 1;
  }
  console.log("map:", map);
  for (var val in map) res++;
  return res;

};
var root = function (parent, i) {
  while (parent[i] != i) i = parent[i];
  return i;
};