Leetcode1319. 连通网络的操作次数(medium,BFS,DFS)_leetcode 1319. 连通网络的操作次数

目录

1. 题目描述

2. 解题分析

3. 代码实现

---

1. 题目描述

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

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

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

示例 1：

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

示例 2：

输入：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

提示：

• 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]
• 没有重复的连接。
• 两台计算机不会通过多条线缆连接。 

2. 解题分析

        connections相当于是图的edge列表表示。

        第一感，这个问题不能以构造性的方式去做，比如说尝试这样或那样挪动边去将整个图变成连通图，然后看那种方案所需要的操作次数最小。应该以类似于数学中的存在性证明的方式来求解。

        （1）假定边的数量足够的条件下，如果原图中有k个孤岛（即k个分离的连通区域），则需要（k-1）条边才能将整个图变成连通图，因此就需要(k-1)次操作。记孤岛数位为。

        （2）在确定了原图孤岛个数后，接下来需要确定原图是否有足够的冗余边用来填补各个孤岛。

        （3）与(1)中的道理相同，要让总共N个节点以最少边数连接起来变成全连通图，至少需要N-1条边。

        因此只需要比较原图中原有边数与节点数是否满足以上（3）的条件即可判断是否有足够多的边。当然，还有一个环节就是，要证明在边数足够的条件下，总是能够以次操作完成挪动并使得网络变成一个全连通图。参见后面第4节。

        岛屿个数的搜索基于邻接列表的表示方式比较方便，所以可以基于connections先构建邻接列表（adjacence list），然后再基于临界列表通过广度或深度搜索搜索岛屿个数。

       

3. 代码实现

from typing import List
from collections import deque
class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
 
        # Construct the adjacency list
        adjList = dict()
        for edge in connections:
            if edge[0] in adjList:
                adjList[edge[0]].append(edge[1])
            else:
                adjList[edge[0]] = [edge[1]]
 
            if edge[1] in adjList:
                adjList[edge[1]].append(edge[0])
            else:
                adjList[edge[1]] = [edge[0]]
        # n_nodes = len(adjList)
        n_edges = len(connections)
        
        # print(adjList)
        
        if n_edges < n-1:
            return -1
        
        # Count the number of islands
        visited = set()
        n_islands = 0
        for k in range(n):
            if k not in visited:
                q = deque()
                q.append(k)
                visited.add(k)
                if k in adjList:
                    while len(q)>0:
                        m = q.pop()
                        # print(k,m,adjList[m])
                        for j,adjnode in enumerate(adjList[m]):
                            if adjnode not in visited:
                                q.append(adjnode)
                                visited.add(adjnode)
                n_islands += 1
        
        return n_islands-1
    
if __name__ == '__main__':
    
    sln = Solution()
    
    n = 4
    connections = [[0,1],[0,2],[1,2]]
    print(sln.makeConnected(n,connections))
        
    n = 6
    connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
    print(sln.makeConnected(n,connections))
    
    n = 6
    connections = [[0,1],[0,2],[0,3],[1,2]]
    print(sln.makeConnected(n,connections))
    
    n = 5
    connections = [[0,1],[0,2],[3,4],[2,3]]
    print(sln.makeConnected(n,connections))

        执行用时：120 ms, 在所有 Python3 提交中击败了71.63%的用户

        内存消耗：35 MB, 在所有 Python3 提交中击败了27.67%的用户

4. 可行性证明

        当图中有k个分离的连通区域，是否一定可以找到一种移动 k−1 根线的操作方法呢？以下是一种构造性的证明（严格证明本身还是有点麻烦的，所以这里直接摘抄leetcode官解证明供大家参考）

        我们可以发现，m 台电脑只需要 m−1 根线就可以将它们进行连接。如果一个节点数为 m 的连通分量中的边数超过 m−1，就一定可以找到一条多余的边，且移除这条边之后，连通性保持不变。此时，我们就可以用这条边来连接两个连通分量，使得图中连通分量的个数减少 1。

        在题目给出的样例 2 中，连通分量 {0,1,2,3} 中有 5 条边，大于 m−1=3。因此一定可以找到一条多余的边。具体地，该连通分量中的任意一条边被移除后，连通性都保持不变。

        注意：并不是在所有的情况下，连通分量中的任意一条边都是可以被移除的，我们只需要保证必定能够找到「一条」多余的边。

        因此我们可以设计一个迭代的过程：每次在图中找出一条多余的边，将其断开，并连接图中的两个连通分量。将这个过程重复 k−1 次，最终就可以使得整个图连通。

        我们如何保证一定能找出「一条」多余的边呢？我们需要证明的是，在任意时刻，如果图中有 k ′  个连通分量且 k'>1，即整个图还没有完全连通，那么一定存在一个连通分量，使得其有一条多余的边：即它的节点数为 m_i，边数为 e_i，并且满足。

        我们可以使用反证法来证明上面的结论。假设所有的连通分量都满足，那么：

 

 

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/solution/lian-tong-wang-luo-de-cao-zuo-ci-shu-by-leetcode-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

        回到主目录：笨牛慢耕的Leetcode每日一解题解笔记(动态更新。。。)