并查集的基本实现和特性

并查集 Disjoint Set。

并查集用来解决组团、配对问题。

基本操作

makeSet(s):建立一个新的并查集,其中包含 s 个单元素集合;

unionSet(x, y):把元素 x 和元素 y 所在的集合合并,要求 x 和 y 所在的集合不相交,如果相交则不合并;

find(x):找到元素 x 所在的集合的代表,该操作也可以用于判断两个元素是否位于同一个集合,只要将它们各自的代表比较一下就可以。

并查集结构

初始化

disjoint_set.png

每一个元素拥有一个 parent 数组指向自己,表示它自己的集合。

查询、合并

disjoint_set2.png

查询:对任何一个元素,向上寻找 parent,直到它的 parent 等于它自己,说明找到领头元素,即集合的代表元素。
合并:找出集合的领头元素,讲 parent[e] 指向 a,或者将 parent[a] 指向 e。

路径压缩

disjoint_set3.png

关系和原来一致,查询时间会快很多。

代码实现

class UnionFind {
  constructor (n) {
    this.count = n;
    this.parent = new Array(n);

    for (let i = 0; i < n; i++) {
      this.parent[i] = i;
    }
  }

  find (p) {
    let root = p;

    while (this.parent[root] != root) {
      root = this.parent[root];
    }

    while (this.parent[p] != p) {
      let x = p;
      p = this.parent[p];
      this.parent[x] = root;
    }

    return root;
  }

  union (p, q) {
    let rootP = this.find(p);
    let rootQ = this.find(q);

    if (rootP === rootQ) return;

    this.parent[rootP] = rootQ;

    this.count--;
  }
}

相关题目

朋友圈(亚马逊、Facebook、字节跳动在半年内面试中考过)

岛屿数量(近半年内,亚马逊在面试中考查此题达到 361 次)

被围绕的区域(亚马逊、eBay、谷歌在半年内面试中考过)

// 朋友圈
// 解法1:DFS、BFS 类似岛屿问题

// DFS Java
class Solution {
  public int findCircleNum (int[][] M) {
    boolean[] visited = new boolen[M.length];
    
    int ret = 0;
    	
    // 使用 visited 数组,依次判断每个节点
    // 如果未访问,朋友圈数加 1 并对该节点进行 dfs 搜索标记所有访问到的节点
    for (int i = 0; i < M.length; i++) {
      if (!visted[i]) {
        dfs(M, visited, i);
        ret++;
      }
    }
    
    return ret;
  }
  
  private void dfs (int[][] m, boolean[] visited, int i) {
    for (int j = 0; j < m.length; j++) {
      if (m[i][j] == 1 && !visited[j]) {
        visited[j] = true;
        dfs(m, visited, j);
      }
    }
  } 
}
# 朋友圈
# 解法2:并查集

# 并查集 Python
class Solution (object):
	def findCricleNum(self, M)
  	  if not M: return 0
    
      n = len(M)
      p = [i for i in range(n)]
      
      for i in range(n):
        	for j in range(n):
            if M[i][j] == 1:
              	self._union(p, i, j)
                
      return len(set[self._parent(p, i) for i in range(n)])
    
    def _union(self, p, i, j):
      p1 = self._parent(p, i)
      p2 = self._parent(p, j)
      p[p2] = p1
      
    def _parent(self, p, i)
    	root = i
      while p[root] != root:
        root = p[root]
      while p[i] != i:
        x = i; i = p[i]; p[x] = root
      return root
// 岛屿数量

/**
 * 深度优先搜索
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  let count = 0;

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === '1') {
        count++;
        trunZero(i, j, grid);
      }
    }
  }

  return count;
};

function trunZero (i, j, grid) {
  if (
    i < 0 || i >= grid.length ||
    j < 0 || j >= grid[0].length || grid[i][j] === '0'
  ) return;

  grid[i][j] = '0';

  trunZero(i, j + 1, grid);
  trunZero(i, j - 1, grid);
  trunZero(i + 1, j, grid);
  trunZero(i - 1, j, grid);
}


/**
 * 广度优先搜索
 * @param {character[][]} grid
 * @return {number}
 */
const numIslands = (grid) => {
  const queue = [];
  
  let count = 0;

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === '1') {
        count++;
        grid[i][j] = '0';
        queue.push([i, j]);
        turnZero(queue, grid);
      }
    }
  }

  return count;
}

function turnZero (queue, grid) {
  const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];

  while (queue.length) {
    const cur = queue.shift();

    for (const dir of dirs) {
      const x = cur[0] + dir[0];
      const y = cur[1] + dir[1];

      if (
        x < 0 || x >= grid.length ||
        y < 0 || y >= grid[0].length ||
        grid[x][y] !== '1'
      ) continue;

      grid[x][y] = '0';

      queue.push([x, y]);
    }
  }
}