JavaScript 并查集

统计信息：字数 17102 阅读35分钟

这部分还需要仔细思考

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。

并查集是合并集合的方式，对于一些关联性的集合，合并查询的方式可以使得题目分类处理，是一种题型的解决方案，这里最关键是构思好集合之间的关联关系。

面试过程中遇到的并不算特别多，所以属于补充的 part。

基本模板

初始化：把每个点所在集合初始化为其自身。这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为 O(N)。

查找：查找元素所在的集合，即根节点。

合并：将两个元素所在的集合合并为一个集合。合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

class UnionFind {
  constructor (n) {
    // 初始化的父节点数组都是指向自己当前的下标的； -- 其中下标是唯一值
    this.parent = new Array(n).fill(0).map((element, index) => index);
  }

  // 合并两个并查集
  union (index1, index2) {
    this.parent[this.find(index2)] = this.find(index1);
  }

  // 寻找 x 的根节点
  find (index) {
    if (this.parent[index] !== index) {
      this.parent[index] = this.find(this.parent[index]);
    }
    return this.parent[index];
  }
}

具体问题上，可能可以简化或者强化 union 方法，来解决具体的问题

题目 547. 省份数量

分析

每一个城市都有可能是一个省份，而只有是连接的城市，就合并为一个省份，最后剩下的集合就是省份 所以可以直接用 parents 数组缓存，其中 index 表示自己的唯一表示，value 表示指向集合城市 当我们遇到 isConnected[i][j] === 1 的时候，将两个城市连接起来，最后得到的值就是连接状况 最后的 parents[index] === index 的数量，就是集合的数量 时间复杂度 O(n), 空间复杂度 O(n)

var findCircleNum = function(isConnected) {
  const len = isConnected.length
  const parents = Array.from(isConnected).map((_,index) => index) // 指向自己

  for(let i = 0;i<len;i++){
    for(let j=0;j<len;j++){
      if(isConnected[i][j] === 1){
        _connect(i,j) // 将 i, j 合并
      }
    }
  }
  return parents.filter((item,index) => item === index).length //筛选出根节点

  function _connect(x,y) {
    parents[_find(x)] = _find(y)
  }

  function _find(x){
    if(parents[x] ===x) return x
    return _find(parents[x])
  }
}

标准写法

// 标准类写法
class UnionFind {
  constructor(n){
    // 缓存两个数组，父节点数组和当前节点的子节点数量数组
    // 1. 初始化的父节点数组都是指向自己当前的下标的； -- 其中下标是唯一值
    this.parents = new Array(n).fill(1).map((_,index) => index)
    // 2. 初始化的子节点数量数组都是只有一个；-- 其中下标是唯一值
    this.sizes = new Array(n).fill(1) // 
  }

  // 寻找 x 的根节点
  find(x){
    if(this.parents[x] === x) return x
    return this.find(this.parents[x])
  }

  // 合并两个并查集
  connect(x,y){
    const px = this.find(x)
    const py = this.find(y)
    if(px === py) return // 如果他们是一个集合，则直接返回
    if(this.sizes[px]>this.sizes[py]){
      // px 挂的节点更多，所以将 py 也挂过来
      this.parents[py] =px
      this.sizes[px]++
    }else{
      this.parents[px] =py
      this.sizes[py]++ 
    }
  }
}

var findCircleNum = function(isConnected) {
  const len = isConnected.length
  const unions = new UnionFind(isConnected.length)
  for(let i = 0;i<len;i++){
    for(let j=0;j<len;j++){
      if(isConnected[i][j] === 1){
        unions.connect(i,j) // 将 i, j 合并
      }
    }
  }
  return new Set(unions.parents).size
}

721. 账户合并

https://leetcode.cn/problems/accounts-merge/

1.题目已知邮箱属于唯一的一个name，而 name 不是唯一的，名字是可以相同也可以不同，所以 name 只能算是一个标记而已，所以一开始做合并操作不需要计算 name，用 email_name_map 缓存起来，直到最后再用。

2.邮箱是一个字符串，而这里显然需要将同一个用户的邮箱缓存到一起，所以这里用下标来标记不同的邮箱，并缓存到 email_index_map

3.开始使用并查集，将同一个用户下 email 连接起来

4.但是具体怎么重新排列，需要通过 email_index_map 来找到找到原始的 email 然后查找是否属于同一个集合的，然后再缓存在一起；

5.所有相同集合的值后缓存在了 email_index_map 的 value 中了，取出来，排序，然后从 email_name_map 取出 name，然后合并成一个数组，然后作为二维数组的一个 item push 到结果数组里

6.时间复杂度 nlogn – 每一次并查集合并的时候，需要进行2次查找，1次合并；空间复杂度 O(n)

var accountsMerge = function(accounts) {

  const email_index_map = new Map()
  const email_name_map = new Map()

  let emailIndex = 0 // 设置下标，作为唯一标识 -- 也代表了 emails 的数量
  for (let i = 0; i < accounts.length; i++) {
    const account = accounts[i];
    const name = account[0]
    for (let j = 1; j < account.length; j++){
      const email = account[j];
      if (!email_index_map.has(email)) {
        email_index_map.set(email, emailIndex)
        email_name_map.set(email, name)
        emailIndex++
      }
    }
  }

  // 并查集
  const parents = Array.from({length:emailIndex}).map((_,index) => index);

  function _find(x){
    if (parents[x] === x) return x
    return _find(parents[x])
  }

  function _connect(x,y) {
    const px = _find(x)
    const py = _find(y)
    parents[py] = px // 让 px 指向 py
  }

  // 开始使用并查集，将同一个用户下 email 连接起来
  for (let i = 0; i < accounts.length; i++) {
    const firstEmail = accounts[i][1];
    const firstIndex = email_index_map.get(firstEmail);
    for (let j = 2;j < accounts[i].length;j++){
      const secondEmail = accounts[i][j];
      const secondIndex = email_index_map.get(secondEmail);
      _connect(firstIndex,secondIndex);
    }
  }

  // 现在每一个 email 的关联关系都通过 index 连接好了，现在需要用一个数据结构将他们取出来
  // 这 key 值是根 emailIndex, values 就是这个集合的 emails 
  const index_email_map = new Map();
  for (let email of email_index_map.keys()) {
    const emailIndex = email_index_map.get(email);
    const root = _find(emailIndex);
    index_email_map.set(root, index_email_map.has(root) ? [...index_email_map.get(root),email] : [email]);
  }

  const merge = [];
  for (let emailsArr of index_email_map.values()){
    emailsArr.sort();
    const name = email_name_map.get(emailsArr[0])
    merge.push([name,...emailsArr])
  }
  return merge;
}

官方解答

https://leetcode.cn/problems/accounts-merge/solution/zhang-hu-he-bing-by-leetcode-solution-3dyq/

var accountsMerge = function(accounts) {
  const emailToIndex = new Map();
  const emailToName = new Map();
  let emailsCount = 0;
  for (const account of accounts) {
    const name = account[0];
    const size = account.length;
    for (let i = 1; i < size; i++) {
      const email = account[i];
      if (!emailToIndex.has(email)) {
        emailToIndex.set(email, emailsCount++);
        emailToName.set(email, name);
      }
    }
  }

  const uf = new UnionFind(emailsCount);
  for (const account of accounts) {
    const firstEmail = account[1];
    const firstIndex = emailToIndex.get(firstEmail);
    const size = account.length;
    for (let i = 2; i < size; i++) {
      const nextEmail = account[i];
      const nextIndex = emailToIndex.get(nextEmail);
      uf.union(firstIndex, nextIndex);
    }
  }

  const indexToEmails = new Map();
  for (const email of emailToIndex.keys()) {
    const index = uf.find(emailToIndex.get(email));
    const account = indexToEmails.get(index) ? indexToEmails.get(index) : [];
    account.push(email);
    indexToEmails.set(index, account);
  }
  const merged = [];
  for (const emails of indexToEmails.values()) {
    emails.sort();
    const name = emailToName.get(emails[0]);
    const account = [];
    account.push(name);
    account.push(...emails);
    merged.push(account);
  }
  return merged;
};

class UnionFind {
  constructor (n) {
    this.parent = new Array(n).fill(0).map((element, index) => index);
  }

  union (index1, index2) {
    this.parent[this.find(index2)] = this.find(index1);
  }

  find (index) {
    if (this.parent[index] !== index) {
      this.parent[index] = this.find(this.parent[index]);
    }
    return this.parent[index];
  }
}

924. 尽量减少恶意软件的传播

1. 创建并查集，并将可以连接在一起的构成一个集合
2. 通过并查集，查找到每个并查集的 root 节点，并用 injectedMap 缓存根节点和对应的缺陷节点数
3. 初始化最大子节点数量 maxSize 和返回值 ret
4. 再次遍历 initial 错误节点，然后找到每个节点对应的根节点出现的次数 count，如果超出1， 那么干掉当前节点 node，依然会有新的节点最后会感染 root 节点，也就是当前集合还是会有感染源；所以没啥意思 如果都是只有一个感染源的集合，那么就判断这个集合的大小，集合越大，则删除当前污染源节点效果更好；如果集合一样大，就删除小的那一个；
5. 时间复杂度 O(n)，空间复杂度 O(n)

var minMalwareSpread = function (graph, initial) {
  const len = graph.length;
  const union = new UnionFind(len);
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (graph[i][j] === 1) {
        union.connect(i, j);
      }
    }
  }

  // 感染源触发的根节点状态map，key 是感染源的根节点，value 是出现次数
  const injectedMap = new Map();

  initial.forEach(node=> {
    const root = union.find(node)
    injectedMap.set(root,injectedMap.get(root)?injectedMap.get(root)+1:1)
  })

  let maxSize = 0; // 符合要求的的集合的数量
  let ret = -1 

  initial.forEach(node => {
    // 找出感染源的根节点
    const root = union.find(node)
    // 找出感染源的根节点出现次数， -- 超出2个源头，就没有删除的效果了
    const count  = injectedMap.get(root)

    if(count === 1){
      const size = union.sizes[root] // 看一下子节点有多少个
      if(size>maxSize || (size === maxSize && node<ret)){
        ret = node
        maxSize = size
      }
    }
  })

  // 如果 ret === -1, 则随便删除一个节点，结果都是一样的，那么就删除其中最小的那个就好了
  if(ret === -1) return Math.min(...initial)
  return ret
};

class UnionFind {
  constructor(len) {
    this.parents = Array.from({ length: len }).map((_, index) => index);
    this.sizes = new Array(len).fill(1);
  }

  find(x) {
    if (x === this.parents[x]) return x;
    return this.find(this.parents[x]);
  }

  connect(x, y) {
    const px = this.find(x);
    const py = this.find(y);
    if (px === py) return;
    if (this.sizes[px] > this.sizes[py]) {
      this.parents[py] = px;
      this.sizes[px] += this.sizes[py];
    } else {
      this.parents[px] = py;
      this.sizes[py] += this.sizes[px];
    }
  }
}

1319. 连通网络的操作次数

对于 n 台电脑，至少需要 n-1 条线才能把他们完全连接前来

对于 n 台机器，如果进行并查集连接后，查看集合的数量，我们最后希望只剩下一个 1 个集合，多出来的集合就是抽取网线进行操作的操作数量

并查集关键降低复杂度的操作 _find， 如果用的是迭代，那么就只需要遍历一遍，否则用递归就还要回来

最终的结果可以在 _connect 连接过程中找出最终集合的大小，也可以根据最后的 parents 的下标和值相等的值来获取

时间复杂度 O(n)

var makeConnected = function (n, connections) {
  const len = connections.length // 网络连接数
  if(len <n -1) return -1 // 如果len 小于 n-1
  const parents = Array.from({length:n}).map((_,index) => index)
  const _find= (x) => {
    if( x !== parents[x]){
      parents[x] = _find(parents[x])
    }
    return parents[x]
  }
  let sizes = n
  const _connect = (x,y) => {
    const px= _find(x)
    const py= _find(y)
    if(px===py) return 
    parents[px] = py
    sizes--
  }
  for(let con of connections){
    _connect(con[0],con[1]) // 连接起来
  }
  return sizes-1
}

1202. 交换字符串中的元素

不断的交换 pairs ，使得最终的字符串 str 是最小的字符串，所以就是要将 pairs 中同一集合的找出来，按顺序排好，然后再组合好

因为同一集合之间可以联通，所以可以经过多次之后，将集合中最小的字符串放在其它字符之前

用一个 root_strArr 来缓存根节点下的字符串数组，然后每次合并的时候，根据 root_strArr 来拍平字符串的缓存，然后缓存两者的数组，最后得到根节点下缓存的集合数组

最后在交换字符串的时候，每一次都找到这个集合剩余的最小的那个值，然后输出出去

超时了

然后以为做了一些细微的优化，比方说字符串比较比较耗时，转成 Unicode 编码； 使自定义的有序数组合并等，但是都超时了

然后分析时间复杂度，如果在连接过程中就进行排序操作，那么复杂度就是 O(n2) n 是 s.length, 而已知 s.length < 10^5, 所以 n2 超出了 10^8, 所以基本不可以通过了；

第一种方法：分析 – 超时了

var smallestStringWithSwaps = function (s, pairs) {
  const parents = Array.from({ length: s.length }).map((_, index) => index);
  const root_strArr = Array.from({ length: s.length }).map((_, index) => [s[index].charCodeAt()]);
  const _find = (x) => {
    if (x !== parents[x]) {
      parents[x] = _find(parents[x]);
    }
    return parents[x];
  };

  const _connect = (x, y) => {
    const px = _find(x);
    const py = _find(y);
    if (px === py) return;
    if (root_strArr[px].length > root_strArr[py].length) {
      parents[py] = px;
      root_strArr[px] =  _connectTwoArr(root_strArr[px],root_strArr[py])
    } else {
      parents[px] = py;
      root_strArr[py]=_connectTwoArr(root_strArr[px],root_strArr[py])
    }
  };

  //  合并两个有序数组
  const _connectTwoArr = (xArr,yArr) => {
    const xLen = xArr.length
    const yLen = yArr.length
    let x = y = 0
    const ret = []
    while(x<xLen && y<yLen){
      if(xArr[x]>yArr[y]){
        ret.push(yArr[y])
        y++
      }else{
        ret.push(xArr[x])
        x++ 
      }
    }
    while(x<xLen) {
      ret.push(xArr[x])
      x++
    }
    while(y<yLen) {
      ret.push(yArr[y])
      y++
    }
    return ret
  }
  for (let p of pairs) {
    _connect(p[0], p[1]);
  }
  let ret = "";
  for (let i = 0; i < s.length; i++) {
    const root = _find(i); // 看一下根节点
    const arr = root_strArr[root]; // 找出这个根节点下的集合，并找出 字典下的最小字符
    const minStr = String.fromCharCode(arr.shift());
    ret += minStr;
  }
  return ret;
};

改进后算法

amazing，上面一直超时，一直想在连接的时候进行排序操作，所以自己进行有序数组的排序，比较转成 unicode 格式的，都超时了 反而在集合合并的时候直接合并数组，然后在一次性将每个集合进行排序，最后得到的结果可以 ac 遍历集合数量，然后进行集合排序，相当于是对所有字符的排序，时间复杂度是 nlogn 其中 n 是 s.length;

var smallestStringWithSwaps = function (s, pairs) {
  const parents = Array.from({ length: s.length }).map((_, index) => index);
  const root_strArr = Array.from({ length: s.length }).map((_, index) => [s[index]]);
  const _find = (x) => {
    if (x !== parents[x]) {
      parents[x] = _find(parents[x]);
    }
    return parents[x];
  };

  const _connect = (x, y) => {
    const px = _find(x);
    const py = _find(y);
    if (px === py) return;
    if (root_strArr[px].length > root_strArr[py].length) {
      parents[py] = px;
      root_strArr[px].push(...root_strArr[py])
    } else {
      parents[px] = py;
      root_strArr[py].push(...root_strArr[px])
    }
  };

  // 连接
  for (let p of pairs) {
    _connect(p[0], p[1]);
  }

  // 各个模块排序
  root_strArr.map(arr => arr.sort());
  let ret = "";
  for (let i = 0; i < s.length; i++) {
    const root = _find(i); // 看一下根节点
    const arr = root_strArr[root]; // 找出这个根节点下的集合，并找出 字典下的最小字符
    const minStr = arr.shift()
    ret += minStr;
  }
  return ret;
};

参考链接：

https://baike.baidu.com/item/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442?fr=aladdin

https://blog.csdn.net/m0_67615103/article/details/128220245

---

Last update: November 9, 2024