2021/01/23 每日一题 连通网络的操作次数

LeetCode上 连通网络的操作次数 ，并查集题目again，记录下解题思路

假设现在传入 n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]] ，有6个节点和5根网线，这里需要确认一个问题，如果网线数量小于节点数-1的数量，那么无论如何都无法连通，那么 connections.length < n - 1 根据题意就会返回-1
根据传入的参数可以画出如下的关系图，会分为[0,1,2,3] [4] [5]三个区域，这3个区域相连需要2条网线，即[0,1,2,3]中多余的两条

根据题意，每两台计算机最多一条线连接且没有重复连接，这里想到并查集，创建n个节点，先是循环 connections = [[0,1],[0,2],[0,3],[1,2],[1,3]] 把每个子数组两点之间先连接起来，即把后一个的 parent 属性设为前一个，之后每次连接都判断两个节点的最顶端父节点是否相同，如果相同那就跳过连接，最后就能把连接图简化成下图所示， [1,2],[1,3] 就是多余的网线，用多出来的两条线用于连接[0,5] [0,4]即可

那么最后需要移动的结果就是能分成几个块，即几个元素的父节点是自己本身，然后用这个数-1得到的值就是最后所求结果

// 定义一个节点
class node {
   constructor (i) {
     // 将自己的父亲设为自己 
     this.parent = this
     // val属性记录下当前节点在accounts中的位置
     this.val = i
   }
}
// 定义查找函数，不断查找父节点，直到父节点等于本身
const find = function (x) {
   while(x !== x.parent) {
      x = x.parent
   }
   return x 
}
var makeConnected = function(n, connections) {
  // 保存connections的长度，即有多少条线
  let len = connections.length
  // 创建n的节点数组
  let nodes = Array(n).fill(0).map((x,i) => new node(i))
  // 需要移动几条线
  let res = 0
  if(len < n-1) return res - 1
  // 遍历循环connections数组，用里面的子数组进行数据连接
  for(let i = 0; i < len; i++) {
     let [x,y] = connections[i]
     
     if(find(nodes[x]) !== find(nodes[y])) {
        // 如果对应的子数组里面的两个节点的父元素不相同，就连接两个元素
        find(nodes[y]).parent = find(nodes[x])
     }
  }
  // 然后需要查询连接完成之后，nodes数组中有几个分块，即有几个元素父元素等于本身
  for(let j = 0; j < nodes.length; j++) {
     if(find(nodes[j]) === nodes[j]) {
        // 如果当前节点的父元素等于本身，即计算有多少个需要连接的点
        res++
     }
  }
  return res - 1
};