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

约 8 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节跳动
标签
深度优先搜索 广度优先搜索 图 并查集
目录

题目描述

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

题意分析

有 n 台编号 0 到 n-1 的计算机，用一批双向线缆 connections 连着，每条线缆是一对 [a, b]。允许的操作是拔掉一条已有线缆，把它插到任意两台计算机之间。问最少做多少次这样的操作能让所有计算机互相连通；如果无论怎么调整都做不到，返回 -1。

关键在于「操作」的性质：它不增加也不减少线缆总数，只改变线缆的位置。所以线缆是一种总量固定的资源，问题实质是「现有资源够不够，以及要挪几根」。

由此得到两条独立的信息。第一，能否连通只取决于线缆总数：n 台机器要全部连通，至少需要 n-1 条线缆（这是树的边数下界，少一条就必然有机器孤立）。第二，要挪几根取决于当前有多少个互不相连的「团」。

还有一个容易被忽略但至关重要的事实：只要线缆总数够 n-1 条，就一定有足够的「冗余线缆」可挪。因为若当前有 c 个团，各团内部最少各用掉「团内点数 - 1」条线缆，合计 n - c 条；总数至少 n-1 >= n-c（c >= 1），差额 >= c-1 条正好够把 c 个团串起来。所以答案永远不会因为「有多余的团但没多余的线」而变成 -1。

约束里 n 可达 $10^5$，connections 长度可达 $10^5$，且题目保证没有重复线缆、没有自环。规模是十万级，说明需要接近线性的做法。

边界要留意四点：connections 可能是空数组，此时只有 n == 1 才连通；输入里可以存在冗余边（两端本就同团），这些边正是可挪动的资源；n == 1 时答案是 0；判 -1 用的是线缆总数，不能用「去重后的有效边数」。

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

核心思路

先判断线缆总数是否足够。连接 n 台计算机至少需要 n - 1 条线缆，因此当 connections.length < n - 1 时，无论如何移动都不可能连通，直接返回 -1。

线缆数量足够后，只需统计当前连通分量数 components。每次把一条冗余线缆改接到两个不同分量之间，分量数恰好减少 1，所以把 components 个分量连成一个至少需要 components - 1 次操作。

这个下界一定能达到。设原图有 m 条边、components 个分量，各分量的生成森林共需要 n - components 条有效边，因此冗余边数为 m - (n - components)。由 m >= n - 1 可得冗余边数至少为 components - 1，足够完成所有连接。

使用并查集统计分量。初始每个节点自成一组，components = n；一条边连接两个不同根时合并并减一，已经同根的边就是冗余边，不改变分量数。

不变量：处理完任意前缀的连接后，并查集中的集合与这些边形成的连通分量一一对应，components 就是集合个数。

正确性：边数不足时由连通图的必要边数可知无解；边数足够时，上述不变量给出真实分量数，而一次操作最多减少一个分量、又有足够冗余边做到每次减少一个，因此最少操作数恰为 components - 1。

解题步骤

  1. 若线缆数小于 n - 1，返回 -1。
  2. 初始化并查集，令每台计算机各自成组，分量数为 n。
  3. 遍历连接；仅当两个端点原本属于不同分量时合并，并将分量数减一。
  4. 返回最终分量数减一。

例如 n = 4、connections = [[0,1],[0,2],[1,2]]：前三台机器属于一个分量，机器 3 单独成组，共两个分量；边 [1,2] 冗余，可改接两个分量，答案为 1。

n = 6 且只有 4 条线缆时，4 < 5，直接返回 -1；n = 1 时 0 < 0 不成立，最终返回 1 - 1 = 0。

代码实现

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(m\alpha(n))$，其中 m 是连接数；路径压缩与按大小合并使单次操作均摊为 $O(\alpha(n))$。
  • 空间复杂度：$O(n)$，用于并查集的父节点与集合大小数组。

关键点总结

  • 先用 m >= n - 1 判断物理资源是否足够，再统计连通分量。
  • 答案是 components - 1，因为一次操作最多合并两个分量。
  • 冗余边无需显式保存；合并失败的边数量由总边数与生成森林边数自动保证足够。
  • 并查集分量计数只在成功合并两个不同根时减一。

易错点总结

  • 用成功合并次数判断线缆是否足够：冗余边正是可以移动的资源，不能从总数中排除。
  • 每处理一条边都减少分量数：环内边不会合并集合，重复减一会低估答案。
  • 边数足够就直接返回 0：边可能集中在局部形成环，仍需计算当前分量数。
  • 答案返回 components：连接 components 个分量只需要 components - 1 条跨分量边。
  • 递归 find 不做任何优化：极端结构可能产生过深调用栈；路径减半与按大小合并更稳妥。

相似题目

题目 难度 考察点
547. 省份数量 中等 输入是邻接矩阵而非边列表，直接返回分量数，不涉及边数够不够的判断
323. 无向图中连通分量的数目 中等 本题去掉「操作次数」外壳后的纯粹版本，只数分量
684. 冗余连接 中等 关注的是「哪条边造成了环」，要在 ra == rb 的分支里返回该边而非忽略它
130. 被围绕的区域 中等 用一个虚拟节点代表「边界」，把「是否与外界连通」转化为同分量判断
990. 等式方程的可满足性 中等 先合并所有等式再逐条校验不等式，体现「先建关系后查询」的两趟套路
721. 账户合并 中等 元素是字符串需先映射成下标，合并后还要按根分组并排序输出
1202. 交换字符串中的元素 中等 同一分量内的字符可任意重排，合并后对每组字符排序即得字典序最小
839. 相似字符串组 困难 边不是给定的，需两两判断相似性建边，代价 $O(n^2 L)$
200. 岛屿数量 中等 网格版连通分量，二维坐标要压成一维下标才能喂给并查集
305. 岛屿数量 II 困难 陆地动态加入，必须用并查集在线维护分量数，DFS 每次重扫会超时
128. 最长连续序列 中等 把相邻整数合并成组，答案取最大 size 而非分量个数
1584. 连接所有点的最小费用 中等 边带权，需按权排序后跑 Kruskal，并查集从「数分量」升级为「筛有效边」
803. 打砖块 困难 并查集只能合并不能拆分，必须离线倒序处理把删除变成添加
785. 判断二分图 中等 需要带权（或扩展域）并查集维护「敌对关系」，也可直接染色 BFS