题目

image.png

思路

  • 并查集
  • 深度优先构建图

    代码

    1. //1.并查集
    2.   int res;
    3.   public int makeConnected(int n, int[][] connections) {
    4.       if (connections.length < n - 1) return -1;
    5.       int[] s = new int[n];
    6.       res = n;
    7.       //初始化
    8.       Arrays.fill(s, -1);
    9.       //构建并查集
    10.       for (int[] connection : connections) {
    11.            union(s, connection[0], connection[1]);
    12.       }
    13.       return res - 1; //因为合并的时候是两个，要在最后结果多减一个
    14.   }
    15.   //合并
    16.   public void union(int[] s, int i, int j) {
    17.       int ri = findFC(s, i), rj = findFC(s, j);
    18.       if (ri != rj) {
    19.           s[ri] = rj;
    20.           //每合并一个说明少一个需要连接
    21.           res--;
    22.       }
    23.   }
    24.   //压缩路径查找，目的是为了降低高度，提高查找速度
    25.   public int findFC(int[] s, int i) {
    26.       if (i < 0 || i >= s.length) return -1;
    27.       if (s[i] < 0) return i;
    28.       s[i] = findFC(s, s[i]);
    29.       return s[i];
    30.   }
    连通网络的操作次数