算法随笔 — 树结构基础 — 并查集

水深无声 2022-10-06 05:53 159阅读 0赞

# 并查集定义 #

并查集是一种用来解决 `连通性` 的数据结构，抽象的方向不同会导致实现方式的不同。

我们也可以用并查集来表示集合的关系。

## 1.快速查找(quick-find) ##

![quick-find][]  
如图所示，我们可以通过给元素加颜色来表示其所属集合，当然颜色只是一种比喻，实际上可以用数字或者其他字符来表示

这种并查集之所以能快速查找是因为查找方法的时间复杂度是O(1)

但是也有一个缺点就是合并比较慢，其合并方法的时间复杂度为O(n)

//* 1.quick-find 快速查找(合并慢)
    //* 将属于同一集合的节点标记为同一颜色
    class Union_quick_find { 
      private readonly colors: number[]
      constructor(n: number) { 
        this.colors = new Array(n).fill(0).map((v, i) => i)
      }
      
      find(index: number) { 
        return this.colors[index]
      }
      
      merge(a: number, b: number) { 
        const cb = this.colors[b]
        // 遍历所有元素，将属于b集合的元素归于a集合的名下
        for (let i = 0; i < this.colors.length; i++) { 
          if (this.colors[i] === cb) this.colors[i] = this.colors[a]
        }
      }
    }

从代码实现层面来看，我们能获得的是一个元素的所属 **集合**

## 2.快速合并 (quick-union) ##

顾名思义，这种并查集在合并操作时效率非常高，而查找的效率在一般的实现下是比较不稳定的，当然后面会有相应的优化方法，先介绍快速合并的并查集如何实现

在这种并查集的实现中，我们用一棵树来表示一个集合，用根节点表示一棵树(也就是一个集合)

初始化时，每个节点就是一棵树(不同树代表不同的集合)

//* 2.quick-union 快速合并
    //* 将连通关系转换为树形结构，通过递归的方式快速判定
    //* 老大通过树的根节点来比较
    class Union_quick_union { 
      private readonly boss: number[]
      constructor(n: number) { 
        this.boss = new Array(n).fill(0).map((v, i) => i)
      }
      
      find(index: number): number { 
        if (this.boss[index] === index) return index
        return this.find(this.boss[index])
      }
      
      merge(a: number, b: number) { 
        const aBoss = this.find(a), bBoss = this.find(b)
        if (aBoss === bBoss) return
        //! 这里没有考虑到两颗树的情况，因此在极端情况下查找效率会非常低
        this.boss[aBoss] = bBoss
      }
    }

从以上代码可以发现，查找方法的效率由树高和节点的位置决定，当查找的节点所在树越高、越处在底层，查找效率越慢

同时，上述代码在合并的时候也欠考虑，比如说合并的树比合并前的树高还要高，这样的结果是增加了查找的负担

那是不是就意味着矮的树合并到高的树上就行了呢？其实，我们应该根据树的平均查找次数来判断才是最公正的  
 树 的 平 均 查 找 次 数 = ∑ 节 点 的 查 找 次 数 节 点 数 树的平均查找次数=\\frac\{\\sum\{节点的查找次数\}\}\{节点数\} 树的平均查找次数=节点数∑节点的查找次数

节点的查找次数表示一棵树从根节点到目标节点需要走的步数

令 有 a 、 b 两 棵 树 ， a 树 有 s a 个 节 点 ， 总 共 有 l a 次 查 找 次 数 b 树 有 s b 个 节 点 ， 总 共 有 l b 次 查 找 次 数 以 a 为 根 的 合 并 树 的 平 均 查 找 次 数 = l a + l b + s b s a + s b 以 b 为 根 的 合 并 树 的 平 均 查 找 次 数 = l a + l b + s a s a + s b 令有a、b两棵树，a树有s\_a个节点，总共有l\_a次查找次数 \\\\ b树有s\_b个节点，总共有l\_b次查找次数 \\\\ 以a为根的合并树的平均查找次数=\\frac\{l\_a+l\_b+s\_b\}\{s\_a+s\_b\} \\\\ 以b为根的合并树的平均查找次数=\\frac\{l\_a+l\_b+s\_a\}\{s\_a+s\_b\} 令有a、b两棵树，a树有sa个节点，总共有la次查找次数b树有sb个节点，总共有lb次查找次数以a为根的合并树的平均查找次数=sa\+sbla\+lb\+sb以b为根的合并树的平均查找次数=sa\+sbla\+lb\+sa  
从以上推导出来的两分式可以看出，节点数大的树的根作为合并树的根的话，合并树的查找次数越少

通俗地说就是节点少的当儿子，因此也有了以下的优化代码

//* 3.weighted-quick-union 加权快速合并
    //* 通过权重考虑平均查找次数，对合并过程进行优化
    //* 权重以节点数量来衡量
    class Union_weighted_quick_union { 
      private readonly boss: number[]
      private readonly size: number[]
      constructor(n: number) { 
        this.boss = new Array(n).fill(0).map((val, i) => i)
        this.size = new Array(n).fill(0).map(_ => 1)
      }
      
      find(index: number): number { 
        if (index === this.boss[index]) return index
        return this.find(this.boss[index])
      }
      
      merge(a: number, b: number) { 
        // 小弟没有话语权，要合并得找大哥
        const aBoss = this.find(a), bBoss = this.find(b)
        if (aBoss === bBoss) return
        // 小树挂在大树上
        if (this.size[aBoss] < this.size[bBoss]) { 
          // a树挂在b树名下
          this.boss[aBoss] = bBoss
          this.size[bBoss] += this.size[aBoss]
        } else { 
          // b树挂在a树名下
          this.boss[bBoss] = aBoss
          this.size[aBoss] += this.size[bBoss]
        }
      }
    }

加权合并是合并策略的优化，查找策略也有优化方法

当我们在查找时，把遍历到的节点都直接挂在根节点下时，那以后再次查找或者查找其他节点的时候，只要经过一步就能到达根节点，这就是 `路径压缩`

使用路径压缩时，查找的时间复杂度接近于 O(1)

//* 4.quick-find-quick-union
    //* 带路径压缩的加权平均
    class Union_quick_find_quick_union { 
      private readonly boss: number[]
      private readonly size: number[]
      constructor(n: number) { 
        this.boss = new Array(n).fill(0).map((v, i) => i)
        this.size = new Array(n).fill(0).map((v, i) => i)
      }
      
      // 在查找的过程中，将挂载的节点扁平化
      find(index: number): number { 
        /* * 递归含义： * 函数意义：把一颗树上的所有节点都挂在另一棵树的子节点上 * 边界条件：当前节点为根节点时，不需要递归 * 递归过程：找到要挂载树的根节点，把当前节点指向为根节点，返回根节点 * */
        if (this.boss[index] === index) return index
        const root = this.find(this.boss[index])
        // 由于是递归调用，因此可以把这棵树上的所有节点都挂在老大的子节点上
        this.boss[index] = root
        return root
      }
      
      merge(a: number, b: number) { 
        const aBoss = this.find(a), bBoss = this.find(b)
        if (aBoss === bBoss) return
        if (this.size[aBoss] < this.size[bBoss]) { 
          this.boss[aBoss] = bBoss
          this.size[bBoss] += this.size[aBoss]
        } else { 
          this.boss[bBoss] = aBoss
          this.size[bBoss] += this.size[aBoss]
        }
      }
    }

这里的查找方法又用到了递归，就当是顺便复习一下了

在做题或比赛的时候，我们通常不会使用上述的几种比较“复杂”(其实也没那么复杂)的代码，而且也不会使用到加权合并，因为光是有路径压缩就已经极大提高效率了，两种优化方法都用相比于只有路径压缩并没有提高多少

所以就有了如下一套简洁并查集模板，在遇到具体问题时在这个基础上稍加变化即可

//* 5.只有路径压缩的并查集模板
    class UnionSet { 
      private readonly boss: number[]
      constructor(n: number) { 
        this.boss = new Array(n).fill(0).map((v, i) => i)
      }
      
      find(index: number): number { 
        return this.boss[index] = this.boss[index] === index ? index : this.find(this.boss[index])
      }
      
      merge(a: number, b: number) { 
        // 直接将a树挂载在b树上
        this.boss[this.find(a)] = this.find(b)
      }
    }

下面的习题我们也会反复使用这个模板

**总结**  
![并查集种类总结][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70]

--------------------

# 习题 #

> ## leetCode 547 省份数量 ##

![leetCode547题目][leetCode547]  
这道题把连接的元素当成一个集合，本质上就是求集合的数量

想到集合，第一时间就想到了交并集

这道题就是交并集的一个简单应用

class UnionSet { 
      private readonly boss: number[]
      constructor(n: number) { 
        this.boss = new Array(n).fill(0).map((v, i) => i)
      }
      
      find(index: number): number { 
        if (this.boss[index] === index) return index
        const root = this.find(this.boss[index])
        this.boss[index] = root
        return root
      }
      
      merge(a: number, b: number) { 
        this.boss[this.find(a)] = this.find(b)
      }
      
      count() { 
        let res = 0
        this.boss.forEach((v, i) => (v === i) && res++)
        return res
      }
    }
    
    function findCircleNum(isConnected: number[][]): number { 
      const len = isConnected[0]?.length
      if (!len) return 0
      const unionSet = new UnionSet(len)
      for (let i = 0; i < isConnected.length; i++) { 
        for (let j = i + 1; j < len; j++) { 
          if (isConnected[i][j] === 1) unionSet.merge(i, j)
        }
      }
      return unionSet.count()
    }

![leetCode547结果][leetCode547 1]

> ## leetCode 200 岛屿数量 ##

![leetCode200题目][leetCode200]  
这道题也是数集合，需要注意的是每次合并只需要判断当前位置的上面和左面(如果有的话)是否需要合并就行了，并不需要同时判断上下左右四个方向，因为该来的迟早会来的

数集合的方法就是判断当前位置元素的父节点是不是自己，如果是自己就代表当前元素就是一个树(集合)的根

class UnionSet { 
      private readonly boss: number[]
      constructor(n: number) { 
        this.boss = new Array(n).fill(0).map((v, i) => i)
      }
      
      find(index: number): number { 
        return this.boss[index] = this.boss[index] === index ? index : this.find(this.boss[index])
      }
      
      merge(a: number, b: number) { 
        this.boss[this.find(a)] = this.find(b)
      }
    }
    
    function numIslands(grid: string[][]): number { 
      const len = grid.length * grid[0]?.length
      if (!len) return 0
      const rowLen = grid[0].length
      const unionSet = new UnionSet(len)
      let res = 0
      
      for (let i = 0; i < grid.length; i++) { 
        for (let j = 0; j < grid[i].length; j++) { 
          if (grid[i][j] === '1') { 
            // 上边
            if (i - 1 >= 0 && grid[i - 1][j] === '1') { 
              unionSet.merge(i * rowLen + j, (i - 1) * rowLen + j)
            }
            // 左边
            if (j - 1 >= 0 && grid[i][j - 1] === '1') { 
              unionSet.merge(i * rowLen + j, i * rowLen + j - 1)
            }
          }
        }
      }
      
      for (let i = 0; i < grid.length; i++) { 
        for (let j = 0; j < rowLen; j++) { 
          if (grid[i][j] === '1' && unionSet.find(i * rowLen + j) === i * rowLen + j) { 
            res++
          }
        }
      }
      return res
    }

![leetCode200结果][leetCode200 1]

> ## leetCode 990 等式方程的可满足性 ##

![leetCode990题目][leetCode990]  
相等关系 => 连通性 => 并查集

首先遍历一遍给出方程，将所有相等关系放在同一集合(合并)

然后再遍历一遍方程，查找不等关系并判断不等关系的双方是否属于同一集合，如果是则冲突，不是则当前不等关系成立

![letCode990结果][letCode990]

> ## leetCode 684 冗余连接 ##

![leetCode684题目][leetCode684]  
这道题也是判断集合问题，所谓冗余连接就是连接的两个元素已经在同一集合里面

所以只要遍历给定边，在连接前先判断连接的两个元素是否已经在同一集合中了，如果已经在了则表示当前连接是冗余连接，否则连接两元素

![leetCode684结果][leetCode684 1]

> ## leetCode 1319 连通网络的操作次数 ##

![leetCode1319题目][leetCode1319]  
这道题目首先要考虑一个边界条件，就是连接数不能少于 n − 1 n-1 n−1，这个道理很简单，比如有三台计算机，要连接起来，就至少要两条网线

然后也是一个数集合的问题，把连通起来的计算机放在同一集合，最后结果就是 集 合 数 − 1 集合数-1 集合数−1

![leetCode1319结果][leetCode1319 1]

> ## leetCode 128 最长连续序列 ##

![leetCode128题目][leetCode128]  
这道题有两种做法，一个是先排序后计算，另一个就是并查集

先说排序的，要排序的话就要先扫描，时间复杂度高达O(nlogn)，但是我们可以通过js的Set进行一定程度的优化

首先遍历输入值，将其依次加入到Set中，Set的特点是无重复，而且查找的时间复杂度是O(1) (本质上就是键名键值相同的对象)

然后再遍历这个Set，当能找到当前值-1的值是不做任何操作，直到当前值是某个序列的头，然后再依次找后续值，记录长度，最后与当前最大值比较

function longestConsecutive(nums: number[]): number { 
      const counterSet = new Set()
      nums.forEach(num => counterSet.add(num))
    
      let longest = 0, current = 1
      for (let num of counterSet) { 
        if (counterSet.has((num as number) - 1)) continue
        while (counterSet.has((num as number) + 1)) { 
          (num as number) += 1
          current++
        }
        longest = Math.max(current, longest)
        current = 1
      }
    
      return longest
    }

![leetCode128结果1][leetCode128_1]  
第二种方法就是使用并查集，所谓连续就是检验数字的连通性，我们可以将连续的数字放在同一个集合上

当然我们需要针对本题对并查集做一些相应的改进，我们需要记录每个树的大小，这个大小就是连续序列的长度

具体做法是：首先需要一个Map用于记录输入数组的值和下标的映射，因为传入数组的值可能很大，所以用下标去记录连通位置比较划算

然后就是遍历传入数组，当我们能从Map中找到当前遍历值的下一位时就连通这两个值的下标

最后返回最大集合大小即题目所求

class UnionSet { 
      private readonly boss: number[]
      private readonly size: number[]
      constructor(n: number) { 
        this.boss = new Array(n).fill(0).map((v, i) => i)
        this.size = new Array(n).fill(0).map(_ => 1)
      }
      
      find(index: number): number { 
        return this.boss[index] = this.boss[index] === index ? index : this.find(this.boss[index])
      }
      
      merge(a: number, b: number) { 
        const bossA = this.find(a), bossB = this.find(b)
        if (bossA === bossB) return
        this.boss[bossA] = bossB
        this.size[bossB] += this.size[bossA]
      }
      
      max() { 
        let res = 0
        this.size.forEach(s => res = s > res ? s : res)
        return res
      }
    }
    
    function longestConsecutive(nums: number[]): number { 
      //* 得到一个无重复的序列
      const counter = new Map()
      nums.forEach((num, index) => { 
        if (!counter.has(num)) counter.set(num, index)
      })
      const unionSet = new UnionSet(nums.length)
      counter.forEach((index, num) => { 
        if (counter.get(num + 1) !== undefined) unionSet.merge(index, counter.get(num + 1))
      })
      return unionSet.max()
    }

![leetCode128结果][leetCode128 1]

> ## leetCode 947 移除最多的同行或同列的石头 ##

![leetCode947题目][leetCode947]  
注意题目一个关键字：**最多的**

为了满足题目要求，我们可以将同行同列的石头连通成一个集合，然后拿掉 石 头 数 量 − 1 石头数量-1 石头数量−1个，也就是一个集合只留一个石头，这样我们就能拿掉尽可能多的石头

最后我们用初始石头总数量减去集合数量就是尽可能地拿走石头的数量

class UnionSet { 
      private readonly boss: number[]
      public setCount: number
      constructor(n: number) { 
        this.boss = new Array(n).fill(0).map((v, i) => i)
        this.setCount = n
      }
      
      find(index: number): number { 
        return this.boss[index] = this.boss[index] === index ? index : this.find(this.boss[index])
      }
      
      merge(a: number, b: number) { 
        const bossA = this.find(a), bossB = this.find(b)
        if (bossA === bossB) return
        this.boss[bossA] = bossB
        this.setCount--
      }
    }
    
    function removeStones(stones: number[][]): number { 
      const stoneSet = new UnionSet(stones.length)
      stones.forEach(([x1, y1], i) => { 
        for (let j = i + 1; j < stones.length; j++) { 
          if (x1 === stones[j][0] || y1 === stones[j][1]) stoneSet.merge(i, j)
        }
      })
      return stones.length - stoneSet.setCount
    }

![leetCode947结果][leetCode947 1]

> ## leetCode 1202 交换字符串中的元素 ##

![leetCode1202题目][leetCode1202]  
这道题需要用并查集和优先队列(小顶堆)来解，解题思路很简单，就是实现起来比较麻烦

首先我们将连通的位置放入并查集，然后将其中的元素都放入小顶堆

最后再按照字母排序一个个吐，将其按顺序放在集合的下标中，最终结果即所求

小顶堆的数据结构如下  
\[string, number\] <==> \[字母, 下标\]  
映射到代码中就是 \[s\[index\], index\]

class SmallHeap { 
      public readonly data: [string, number][]  // [字母, 下标]
      constructor(data?: [string, number][]) { 
        this.data = data || []
        this.init()
      }
      
      init() { 
        for (let i = 1; i < this.data.length; i++) this.sortUp(i)
      }
      
      peek() { 
        return this.data[0]
      }
      
      pop() { 
        if (!this.data.length) return null
        if (this.data.length === 1) return this.data.pop()
        const res = this.data[0]
        this.data[0] = this.data.pop() as [string, number]
        this.sortDown(0)
        return res
      }
      
      sortUp(index: number) { 
        let parentIndex: number
        while (index) { 
          parentIndex = (index - 1) >> 1
          if (this.data[index][0] < this.data[parentIndex][0]) this.swap(index, parentIndex)
          else return
          index = parentIndex
        }
      }
      
      sortDown(index: number) { 
        let leftIndex: number, rightIndex: number, target: number
        while (index < this.data.length) { 
          target = index
          leftIndex = (index << 1) + 1
          rightIndex = (index << 1) + 2
          if (leftIndex < this.data.length && this.data[leftIndex][0] < this.data[target][0]) target = leftIndex
          if (rightIndex < this.data.length && this.data[rightIndex][0] < this.data[target][0]) target = rightIndex
          if (index === target) return
          this.swap(index, target)
          index = target
        }
      }
      
      swap(i: number, j: number) { 
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
      }
    }
    
    class UnionSet { 
      public readonly data: number[]
      constructor(n: number) { 
        this.data = new Array(n).fill(0).map((v, i) => i)
      }
      
      find(index: number): number { 
        return this.data[index] = this.data[index] === index ? index : this.find(this.data[index])
      }
      
      merge(a: number, b: number) { 
        this.data[this.find(a)] = this.find(b)
      }
    }
    
    function smallestStringWithSwaps(s: string, pairs: number[][]): string { 
      const res = new Array(s.length)
      const unionSet = new UnionSet(s.length)
      const setMap: { [key: number]: [string, number][]} = { }  // [字母, 下标]
      let queue: SmallHeap
      
      pairs.forEach(([x, y]) => unionSet.merge(x, y))
      const dataSet = [...unionSet.data]  // 获得每个集合的成员分布
      
      // 按集合分类进行遍历
      dataSet.forEach((data, index) => { 
        if (!setMap[unionSet.find(data)]) setMap[unionSet.find(data)] = []
        setMap[unionSet.find(data)].push([s[index], index])
      })
      
      let data: string[] = []
      let indexes: number[] = []
      let temp = 0
      for (let set in setMap) { 
        // 对每个集合的字母进行排序
        queue = new SmallHeap(setMap[set])
        // 将排序好的字母复制到对应的位置上
        while (queue.data.length) { 
          data.push(queue.peek()[0])
          indexes.push(queue.peek()[1])
          queue.pop()
        }
        indexes.sort((i, j) => i - j)
        while (indexes.length) { 
          temp = indexes.pop() as number
          res[temp] = data.pop()
        }
      }
      return res.join('')
    }

![leetCode1202结果][leetCode1202 1]

> ## leetCode 765 情侣牵手 ##

![leetCode765题目][leetCode765]  
观察规律可得，情侣数字右移1位得到的数字相同，因此我们创建的并查集只需要输入数组的一半(总共的情侣对数)，初始化一对情侣就是一个集合

比如0和1向右位移一位得到的数字是0，因此我们把0和1称为第0对情侣，后面的以此类推

针对这道题，我们创建的并查集还需要有一个变量 setCount，该变量初始化为并查集大小，每进行一次合并操作则自减1，这个变量的含义是：不需要交换座位的情侣

题目求的是交换的次数，所以我们只要遍历传入数组，每次取两位进行并查集的合并操作，如果取的两位是属于同一对的情侣，则没有任何操作；如果取的是来自两对的情侣，则进行一次合并(不需要交换座位的情侣数-1)

class UnionSet { 
      private readonly boss: number[]
      private setCount: number
      constructor(n: number) { 
        this.boss = new Array(n).fill(0).map((v, i) => i)
        this.setCount = n
      }
      
      find(index: number): number { 
        return this.boss[index] = this.boss[index] === index ? index : this.find(this.boss[index])
      }
      
      merge(a: number, b: number) { 
        const bossA = this.find(a), bossB = this.find(b)
        if (bossA === bossB) return
        this.boss[this.find(a)] = this.find(b)
        this.setCount--
      }
      
      count() { 
        return this.setCount  // 不需要变换座位对数
      }
    }
    
    function minSwapsCouples(row: number[]): number { 
      const couples = row.length >> 1 // 总对数
      const unionSet = new UnionSet(couples)
      for (let i = 0; i < row.length; i += 2) { 
        unionSet.merge(row[i] >> 1, row[i + 1] >> 1)
      }
      return couples - unionSet.count() // 总对数 - 不需要变换座位的对数
    }

![leetCode765结果][leetCode765 1]

> ## leetCode 685 冗余连接II ##

![leetCode685题目][leetCode685]  
这道题要考虑三种异常情况

*  某个节点有两个父节点 (targetNode !== parent\[targetNode\])  
    ![leetCode685异常1][leetCode685_1]
 *  闭环 (u.find(targetNode) === u.find(parentNode))  
    ![leetCode685异常2][leetCode685_2]
 *  异常边的目标节点有两个父节点，而且形成闭环  
    ![leetCode685异常3][leetCode685_3](蓝色代表边出现顺序)

联结操作如下

parent[targetNode] = parentNode
    u.merge(targetNode, parentNode)

在遍历时，我们需要记录出现双父节点的边和形成闭环的边

然后就要找有问题的边，查找顺序如下

1.  如果没有双重父节点，则直接返回形成闭环的边
2.  如果有环路和双重父节点，则返回 \[双重父节点的节点沿着形成闭环的边找到的父节点, 双重父节点\]  
    如以上最后一个异常情况的 \[2, 1\]
3.  只有双重父节点没有闭环，则直接返回形成双重父节点的边

class UnionSet { 
      private readonly boss: number[]
      constructor(n: number) { 
        this.boss = new Array(n).fill(0).map((v, i) => i)
      }
      
      find(index: number): number { 
        return this.boss[index] = this.boss[index] === index ? index : this.find(this.boss[index])
      }
      
      merge(a: number, b: number) { 
        const bossA = this.find(a), bossB = this.find(b)
        if (bossA === bossB) return
        this.boss[bossA] = bossB
      }
    }
    
    function findRedundantDirectedConnection(edges: number[][]): number[] { 
      let res: number[] = []
      const nodeCount = edges.length
      // 数组从0开始，这里申请n+1的长度是为了方便计算
      const parent = new Array(nodeCount + 1).fill(0).map((v, i) => i)
      const unionSet = new UnionSet(nodeCount + 1)
      
      let twoParentsEdgeIndex = -1, cycleEdgeIndex = -1
      edges.forEach(([parentNode, targetNode], index) => { 
        if (targetNode !== parent[targetNode]) { 
          // 两个父节点
          twoParentsEdgeIndex = index
        } else if (unionSet.find(targetNode) === unionSet.find(parentNode)){ 
          // 闭环
          cycleEdgeIndex = index
        } else { 
          // 目标节点既不会有两个父节点，也不会形成闭环
          parent[targetNode] = parentNode
          unionSet.merge(targetNode, parentNode)
        }
      })
      
      // 找有问题的边
      if (twoParentsEdgeIndex === -1) { 
        // 没有双重父节点，直接返回环路
        return edges[cycleEdgeIndex]
      } else { 
        // 记录有双重父节点的边
        const conflictEdge = edges[twoParentsEdgeIndex]
        if (cycleEdgeIndex >= 0) { 
          // 有环路和双重父节点
          return [parent[conflictEdge[1]], conflictEdge[1]]
        }
        // 只有双重父节点，没有环路
        return conflictEdge
      }
    }

![leetCode685结果][leetCode685 1]

--------------------

# 结语 #

这段时间在忙毕业论文和答辩的事情只能忙里偷闲写算法题，感觉真的很不容易

原来计划是先出来工作一段时间，然后看情况考研考个人工智能专业，但是现在写个本科论文都已经很累了，真的要考研究生的话能考上毕业也很难，感觉自己真的不适合搞学术。。。

还是脚踏实地先精通前端，然后慢慢往架构、全栈方面发展吧

[quick-find]: /images/20221005/1af42776c8874dcaac8f389b1cce69c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70]: /images/20221005/39c584f8cd2143ee82ec19babb27a861.png
[leetCode547]: /images/20221005/3e0301db53e24dc2beafff48b3238b5e.png
[leetCode547 1]: /images/20221005/c9caf74febcd45dca40136de2ad2b4ea.png
[leetCode200]: /images/20221005/8abea6c72f57465b9a8ae200e2d35019.png
[leetCode200 1]: /images/20221005/54b0cf8115a6443580ddf97f031a0736.png
[leetCode990]: /images/20221005/94ac8d29e0e2434d8538bf8ff40a63c4.png
[letCode990]: /images/20221005/aeef143894d747c9b6bcc786d5e3e801.png
[leetCode684]: /images/20221005/1a0058d1570545ee95c2a4b73fc719d0.png
[leetCode684 1]: /images/20221005/c5bb330000614c3da2c2a8fddb297458.png
[leetCode1319]: /images/20221005/c0b05f7809da43318ca61fc009474d62.png
[leetCode1319 1]: /images/20221005/5320e6441eb54c70830817d0ec708e40.png
[leetCode128]: /images/20221005/0d8d601b0db24d179ad1d9ee3184b283.png
[leetCode128_1]: /images/20221005/1c29e9dceb8d4a90b4086f20500b2bcf.png
[leetCode128 1]: /images/20221005/c491af734a0642bd84575308b42bbd0b.png
[leetCode947]: /images/20221005/8c8af46dbf73415d916151d9094b73e1.png
[leetCode947 1]: /images/20221005/98935228e85d41cda3e3587c3f11492c.png
[leetCode1202]: /images/20221005/055f5ea916fb4b9b847ca4097627597c.png
[leetCode1202 1]: /images/20221005/0e7781c6f73d436bb8ad1152324516e3.png
[leetCode765]: /images/20221005/10fb303ed99c423399c55ee9bef19fff.png
[leetCode765 1]: /images/20221005/e6e75205260e419d9a58b68fb6865140.png
[leetCode685]: /images/20221005/6ef13ee532c0470e8de7b75ecf820c44.png
[leetCode685_1]: /images/20221005/4a1527beb3f8412da60a87d2e311a011.png
[leetCode685_2]: /images/20221005/ef400a811ba843a0aeafeaaa6ee1ef71.png
[leetCode685_3]: /images/20221005/afbd24875f014d40b6c183febdcb62e8.png
[leetCode685 1]: /images/20221005/c1badb4e09684ea8882588c76d32b46b.png