LeetCode 1319. 连通网络的操作次数

2023-04-23 HGNULB 约 6 分钟

文章信息 6 个分类 · 4 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 字节

标签

深度优先搜索 广度优先搜索 图 并查集

题目描述

✅ 1319. 连通网络的操作次数

题意分析

n 台计算机由现有线缆连接，一次操作可以拆下一条已有线缆，再接到另一对计算机之间。求使任意两台计算机都能直接或间接通信的最少操作次数，无法做到时返回负一。

只能改接，不能增加线缆总数。最终不要求任意两台都有直接连接，只要求整个网络连通；已经连通的部分可以保留内部必要连接，把冗余线缆拿去连接其他部分。

解法：并查集统计连通分量

核心思路

[!blue]

将计算机看作节点、线缆看作无向边。连接 n 个节点至少需要 n - 1 条边，因此总线缆数 m < n - 1 时，无论如何改接都不够，可以直接判无解。

若当前网络分成 c 个连通分量，每次把一条线缆接到两个不同分量之间，最多让分量数减一。从 c 变成一至少需要 c - 1 次，这是操作次数下界。

边数足够时一定能达到这个下界。每个分量内部只保留一棵生成树，所有分量合计需要 n - c 条边；其余 m - (n - c) 条线缆可以拆走而不破坏原分量。由 m >= n - 1 得到冗余量至少为 c - 1，逐条连接不同分量即可完成。

因此不必实际决定拆哪条、接哪里，只需统计 c。并查集初始让每个节点独立，components = n；读到一条边时寻找两端代表根，根不同就合并并减一，根相同则已有路径相连，这条边不减少分量数。

代码在查找时压缩路径，合并时把较小集合挂到较大集合下，避免代表链过深。处理完全部边，返回 components - 1；已连通时分量数为一，答案自然为零。

解题步骤

1. 现有线缆数小于 n - 1 时返回负一。
2. 创建并查集，父节点指向自身，集合大小为一，分量数为 n。
3. 遍历每条边，查找两端根；相同则跳过，不同则按大小合并并减少分量数。
4. 全部连接处理后，返回剩余分量数减一。

代码实现

class Solution {
    public int makeConnected(int n, int[][] connections) {
        // 线缆总数不能增加，少于生成树所需数量就无解。
        if (connections.length < n - 1) {
            return -1;
        }

        UnionFind unionFind = new UnionFind(n);

        for (int[] connection : connections) {
            unionFind.union(connection[0], connection[1]);
        }

        return unionFind.components - 1;
    }

    private static class UnionFind {
        private final int[] parent;
        private final int[] size;
        private int components;

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            components = n;

            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }

            return x;
        }

        void union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);

            // 同一分量内的边不减少分量数，可作为可移动的冗余资源。
            if (rootA == rootB) {
                return;
            }

            if (size[rootA] < size[rootB]) {
                int temp = rootA;

                rootA = rootB;
                rootB = temp;
            }

            parent[rootB] = rootA;
            size[rootA] += size[rootB];
            // 只有两个不同集合成功合并，分量数才减一。
            components--;
        }
    }
}

type unionFind struct {
    parent     []int
    size       []int
    components int
}

func newUnionFind(n int) *unionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        size[i] = 1
    }
    return &unionFind{parent: parent, size: size, components: n}
}

func (uf *unionFind) find(x int) int {
    for x != uf.parent[x] {
        uf.parent[x] = uf.parent[uf.parent[x]]
        x = uf.parent[x]
    }
    return x
}

func (uf *unionFind) union(a, b int) {
    rootA, rootB := uf.find(a), uf.find(b)
    // 同一分量内的边不减少分量数，可作为可移动的冗余资源。
    if rootA == rootB {
        return
    }
    if uf.size[rootA] < uf.size[rootB] {
        rootA, rootB = rootB, rootA
    }
    uf.parent[rootB] = rootA
    uf.size[rootA] += uf.size[rootB]
    // 只有两个不同集合成功合并，分量数才减一。
    uf.components--
}

func makeConnected(n int, connections [][]int) int {
    // 线缆总数不能增加，少于生成树所需数量就无解。
    if len(connections) < n-1 {
        return -1
    }

    uf := newUnionFind(n)
    for _, connection := range connections {
        uf.union(connection[0], connection[1])
    }
    return uf.components - 1
}

复杂度分析

• 时间复杂度：$O(n + m\alpha(n))$，初始化处理 n 个节点，随后合并 m 条边；路径压缩与按大小合并的均摊代价由反阿克曼函数 $\alpha(n)$ 表示。
• 空间复杂度：$O(n)$，保存父节点、集合大小及分量计数。

关键点总结

[!green]

• 冗余边是可移动的资源，不能从总线缆数中丢掉。
• 成功合并两个集合才减少分量数。
• 边数足够保证能够达到 c-1 次的下界。

易错点总结

[!yellow]

• 每读一条边都减少分量数：环内边并未连接两个分量。
• 边数足够就返回 0：还可能存在孤立的分量。
• 用成功合并边数判断资源是否足够：忽略了可以挪走的冗余边。

相似题目

题目	难度	关联与区别
323. 无向图中连通分量的数目	中等	先统计现有连通分量，若总线缆足够，连接c个分量至少需要c-1次操作。
684. 冗余连接	中等	形成环的冗余边可以移走而不破坏当前分量，用于连接其他分量。
547. 省份数量	中等	用并查集合并连通分量；本题统计网络连通分量与可用冗余边，该题按邻接矩阵合并城市。
721. 账户合并	中等	用并查集合并连通分量；本题统计网络连通分量与可用冗余边，该题按共享邮箱合并账户。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/82209747

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！