题目

题目来源：力扣（LeetCode）

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

示例 1：
image.png

输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。

示例 2：
image.png

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2

示例 3：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。

示例 4：

输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0

思路分析

当计算机的数量为 n 时，我们至少需要 n - 1 根线才能将它们进行连接。如果线的数量少于 n - 1，那么我们无论如何都无法将这 n 台计算机进行连接。因此如果数组 connections 的长度小于 n - 1，那么我们可以直接返回 -1 作为答案。

那么我们如何计算最少的操作次数呢？我们将 n 台计算机看成是 n 个节点，那么初始时，存在 n 个连通分量，然后遍历 connections 数组，将所有的连通分量进行合并，每成功进行一次合并操作，连通分量就会减少 1。遍历结束后，剩余的连通分量减去 1，就是最少的操作次数。

  1. /**
  2.  * @param {number} n
  3.  * @param {number[][]} connections
  4.  * @return {number}
  5.  */
  6. var makeConnected = function(n, connections) {
  7.   // 如果边的数量小于 n - 1，则无论如何都无法连接所有的节点
  8.   if (connections.length < n -1) {
  9.     return -1;
  10.   }
  12.   let  uf = new UnionFind(n);
  13.   // 遍历 connections，将所有的节点进行合并
  14.   for (const conn of connections) {
  15.     uf.unite(conn[0], conn[1]);
  16.   }
  17.   // 遍历结束时，剩余的连通分量 setCount - 1 即为最少操作次数
  18.   return uf.setCount - 1;
  19. };
  21. // 并查集
  22. class UnionFind {
  23.   constructor(n) {
  24.     // 元素所指向的父节点，parent[i] 表示第 i 个元素所指向的父节点
  25.     // 初始化时, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
  26.     this.parent = new Array(n).fill(0).map((value, index) => index);
  27.     // 树的层数，rank[i] 表示以 i 为根的集合所表示的树的层数
  28.     this.rank = new Array(n).fill(1);
  29.     // 节点的个数
  30.     this.setCount = n;
  31.   }
  33.   // 查找过程，查找元素 index 所在集合的编号(查找树的根节点)
  34.   findSet(index) {
  35.     // 不断去查询自己的父节点，直至根节点
  36.     // 根节点的标志是父节点就是本身  parent[index] == index
  37.     if (this.parent[index] != index) {
  38.       // 递归获取节点的父节点
  39.       this.parent[index] = this.findSet(this.parent[index]);
  40.     }
  41.     // 返回根节点
  42.     return this.parent[index];
  43.   }
  45.   // 合并两个集合
  46.   unite(index1, index2) {
  47.     let root1 = this.findSet(index1);
  48.     let root2 = this.findSet(index2);
  49.     // 根节点不一样，是两个不同的集合(两棵不同的树)
  50.     if (root1 != root2) {
  51.       // 根据树的层数合并集合
  52.       // 
  53.       if (this.rank[root1] < this.rank[root2]) {
  54.         // 这个判断如果 root2 所在树的层数 大于 root1，就交换两个父节点，这样始终让 root1 为父节点
  55.         [root1, root2] = [root2, root1];
  56.       }
  57.       // 将层数多的集合合并到集合少的集合
  58.       this.parent[root2] = root1;
  59.       this.rank[root1] += this.rank[root2];
  60.       this.setCount--;
  61.     }
  62.   }
  64.   getCount() {
  65.     return this.setCount;
  66.   }
  68.   connected(index1, index2) {
  69.     return this.findSet(index1) === this.findSet(index2);
  70.   }
  71. }