【每日一题】 1319. 连通网络的操作次数

清疚 2023-01-10 13:30 118阅读 0赞

# 【每日一题】 1319. 连通网络的操作次数 #

> 避免每日太过咸鱼，一天搞定一道LeetCode算法题

## 一、题目描述 ##

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections\[i\] = \[a, b\] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

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

**提示：**

*  1 <= n <= 10^5
 *  1 <= connections.length <= min(n\*(n-1)/2, 10^5)
 *  connections\[i\].length == 2
 *  0 <= connections\[i\]\[0\], connections\[i\]\[1\] < n
 *  connections\[i\]\[0\] != connections\[i\]\[1\]
 *  没有重复的连接。
 *  两台计算机不会通过多条线缆连接。

**示例 1：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]

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

**示例 2：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 1]

输入：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
    解释：线缆数量不足。

## 二、题解 ##

### 1. 解法 ###

### **解题思路：** ###

我们首先考虑在什么情况下，不可能将所有计算机进行连接。

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

#### 1. 解法一 ####

之前我们学习了并查集，所以这次我们就先用并查集的方式来尝试，看能够解决。

我们可以使用并查集来得到图中的连通分量数。

并查集本身就是用来维护连通性的数据结构。如果其包含 n个节点，那么初始时连通分量数为 n，每成功进行一次合并操作，连通分量数就会减少 1。

**java代码实现如下：**

public static void main(String[] args) { 
        int[][] connections = new int[][]{ { 0, 1}, { 0, 2}, { 3, 4}, { 2, 3}};
        int n = 5;
        int i = makeConnected(n, connections);
        System.out.println("输出：" + i);
    }
    
    public static int makeConnected(int n, int[][] connections) { 
        // 线的条数肯定等于机器台数-1 否则不够
        if (n - connections.length > 1) { 
            return -1;
        }
    
        DisjointSetUnion disjointSetUnion = new DisjointSetUnion(n);
        for (int[] connection : connections) { 
            disjointSetUnion.unionSet(connection[0], connection[1]);
        }
    
        return disjointSetUnion.n - 1;
    }
    
    static class DisjointSetUnion { 
    
        int n;
        int[] f;
        int[] rank;
    
        // 初始化
        public DisjointSetUnion(int n) { 
            this.n = n;
            this.f = new int[n];
            this.rank = new int[n];
            for (int i = 0; i < n; i++) { 
                f[i] = i;
                rank[i] = 1;
            }
        }
    
        /** * 找到传入x节点的root节点 * * @param x 顶点 * @return root节点 */
        public int find(int x) { 
            return f[x] == x ? x : (f[x] = find(f[x]));
        }
    
        /** * 判断传入的顶点是否在图中形成回路 */
        public boolean unionSet(int x, int y) { 
            //查找x y的root节点
            int fx = find(x), fy = find(y);
    
            //形成回路
            if (fx == fy) { 
                return true;
            }
    
            // 比较fx和fy两个根节点的深度 把小的父节点设置给大的一个
            if (rank[fx] <= rank[fy]) { 
                f[fx] = fy;
            } else { 
                f[fy] = fx;
            }
            // 联通一个节点就减一
            n--;
            // 应为两个树的深度相同，所以合并后父节点的树深度会增加1
            if (rank[fx] == rank[fy] && fx != fy) { 
                rank[fy]++;
            }
            return false;
        }
    }

复杂度分析

*  时间复杂度：O(m⋅α(n))，其中 mm 是数组 connections 的长度，α 是阿克曼函数的反函数。
 *  空间复杂度：O(n)，即为并查集需要使用的空间。

#### 2. 解法二 ####

做题不是目的，毕竟这道题用并查集做出来也是比较ok的了，但是为了学习更多的算法思想，所以看看大佬们其他的解决方案，了解到了 **深度优先搜索** ，接下来我们就是这个试一下吧。使用深度优先搜索来得到图中的连通分量数。

具体地，初始时所有节点的状态均为「待搜索」。我们每次选择一个「待搜索」的节点，从该节点开始进行深度优先搜索，并将所有搜索到的节点的状态更改为「已搜索」，这样我们就找到了一个连通分量。

List<Integer>[] edges;
    boolean[] used;
    
    public  int makeConnected2(int n, int[][] connections) { 
        if (connections.length < n - 1) { 
            return -1;
        }
    
        edges = new List[n];
        for (int i = 0; i < n; ++i) { 
            edges[i] = new ArrayList<Integer>();
        }
        for (int[] conn : connections) { 
            edges[conn[0]].add(conn[1]);
            edges[conn[1]].add(conn[0]);
        }
    
        used = new boolean[n];
        int ans = 0;
        for (int i = 0; i < n; ++i) { 
            if (!used[i]) { 
                dfs(i);
                ++ans;
            }
        }
    
        return ans - 1;
    }
    
    public  void dfs(int u) { 
        used[u] = true;
        for (int v : edges[u]) { 
            if (!used[v]) { 
                dfs(v);
            }
        }
    }

复杂度分析

*  时间复杂度：O(n+m)，其中 m 是数组 connections 的长度。
 *  空间复杂度：O(n+m)，其中 O(m) 为存储所有边需要的空间，O(n) 为深度优先搜索中使用的栈空间。

题目来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/distance-between-bus-stops

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/011ab34b1a3e416e949e0890ffff7033.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/23f7daaf3044463691e0369c9b5642d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: /images/20221119/3f9f6b1904ee46749d31ad61d2a511b4.png