2021/01/07 每日一题 省份数量

LeetCode上 省份数量 ，记录下解题思路
这里使用了 并查集 的思路，这里有个比较好的文章 并查集详解 可以看看
假如传入 [[1,1,0],[1,1,0],[0,0,1]]
循环建立一个数组，数组每个元素是一个对象，保存当前的index以及元素的父亲（这里将父亲设为自己）
对于上面的数组创建的对象如下，这里的Node永远指向自己

接下来需要做的操作是一个双重for循环，对应取出第一个子数组，因为每个数组中都要保存和所有节点的关系，连接就是1，不连接就是0

 // 对传入的数组中的每个元素进行循环
    for (let i = 0; i < M.length; i++) {
      // 对每个子元素的元素循环，双数组循环
      for (let j = 0; j < M.length; j++) {
         // 如果这个元素是存在的
          if (M[i][j]) {
              xRoot = find(arr[i])
              yRoot = find(arr[j])
              xRoot.parent = yRoot
          } 
      }
    }

i=0 j=0 执行find(arr[0])和find(arr[0])，这里arr[0]的parent都没有更改

i=0 j=1 执行find(arr[0])和find(arr[1])，这里arr[0]和arr[1]的parent也没有更改，但 find(arr[i]).parent = find(arr[j]) 的操作让，arr[0].parent = arr[1]了

i=0 j=2 M[0][2]不存在不进入操作
此时整个arr为

[
{val:0,parent:{val:1,parent:Node}},
{val:1,parent:{val:1,parent:Node}},
{val:2,parent:{val:2,parent:Node}}
]

第一次外层循环结束
i=1 j=0 执行find(arr[1])和find(arr[0])，arr[1]的parent还是arr[1]自己，arr[0]的parent因为第一次外层循环变为arr[1]了，在 find 中就要进行递归操作，寻找arr[1]的parent，这里也还是本身，那么就返回arr[1]，所以最后````find(arr[i]).parent = find(arr[j])```的操作还是将arr[1]的parent设为arr[1]。

i=1 j=1 执行find(arr[1])和find(arr[1])，arr[1]的parent是arr[1]自己，无操作

i=1 j=2 M[0][2]不存在不进入操作
第二次外层循环结束
i=2 j=0 M[2][0]不存在不进入操作

i=2 j=1 M[2][1]不存在不进入操作

i=2 j=2 执行find(arr[2])和find(arr[2])，arr[1]的parent还是arr[1]自己，所以最后也没有对arr[2]进行更改。
第三次外层循环结束
至此arr数组对象已经连接完成，接下来只要遍历arr数组，找到内部对象有多少个的元素父节点还是自己的节点个数，那么这些节点数就是所求。
用一个for循环就能搞定

上图就是根据最后的arr画的图，我们只要计算有几个元素的parent是本身就可以了

---

var findCircleNum = function (M) {
   // 查找父元素函数
     let find = function (x) {
     if (x !== x.parent)
         return find(x.parent)
     return x.parent
   }
   // 节点类
   class Node {
      constructor (val) {
         // 储存当前节点对应的index
         this.val = val
         // 节点的parent
         this.parent = this
      }
   }
    // 创建一个M长度数组，这个数组的每个元素都是一个Node对象
    // 所有元素的父元素都是自己本身
    const arr = []
    for (let i = 0; i < M.length; i++) {
        arr[i] = new Node(i)
    }
    // 对传入的数组中的每个元素进行循环
    for (let i = 0; i < M.length; i++) {
      // 对每个子元素的元素循环，双数组循环
      for (let j = 0; j < M.length; j++) {
         // 如果这个元素是存在的
          if (M[i][j]) find(arr[i]).parent = find(arr[j])
      }
    }
    // res是结果
    let res = 0
    // 用tmp来记录
    // 开始遍历arr数组
    for (let i = 0; i < arr.length; i++) {
      // 如果当前元素的父元素是本身，那么这个就是最中心的那个，有多少个元素这个就有多少个结果
      if(arr[i].parent === arr[i]) res++
    }
    // 返回结果
    return res
};