【Day 78 】2024-06-24 - 1319. 连通网络的操作次数

[azl397985856]

1319. 连通网络的操作次数

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/

前置知识

暂无

题目描述

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

[lxy1108]

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        graph = collections.defaultdict(list)
        for edge in connections:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
        seen = set()
        groups, extra = 0, 0
        for i in range(n):
            if i in seen:
                continue
            seen.add(i)
            queue = [i]
            curnode, curedge = 1,0
            while queue:
                node = queue.pop()
                for child in graph[node]:
                    curedge+=1
                    if child not in seen:
                        curnode+=1
                        seen.add(child)
                        queue.append(child)
            groups += 1
            extra += max(0, curedge//2-curnode+1)
        if extra>=groups-1:
            return groups-1
        else:
            return -1

[franklinsworld666]

代码

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        cnt, size = 0, n
        p = list(range(n))
        for a, b in connections:
            if find(a) == find(b):
                cnt += 1
            else:
                p[find(a)] = find(b)
                size -= 1
        return -1 if size - 1 > cnt else size - 1

[Dtjk]

class Solution { public: int makeConnected(int n, vector<vector>& connections) { if (connections.size() < n - 1) { return -1; }

    vector<int> fa(n);
    iota(fa.begin(), fa.end(), 0);    

    function<int(int)> findset = [&](int x) {return x == fa[x] ? x : fa[x] = findset(fa[x]);};
    int part = n;
    for (auto&& c: connections) {
        int p = findset(c[0]), q = findset(c[1]);
        if (p != q) {
            --part;
            fa[p] = q;
        }
    }

    return part - 1;
}

};