当前位置：首页 > news >正文

图论专题(二十一)：并查集的“工程应用”——拔线重连，修复「连通网络」 - 指南

news 2026/3/26 21:12:50

图论专题(二十一)：并查集的“工程应用”——拔线重连，修复「连通网络」 - 指南

哈喽各位，我是前端小L。

欢迎来到我们的图论专题第二十一篇！在现实世界的网络工程中，资源往往是有限的。如果我们发现公司里的电脑网络分成了好几个互不相通的局域网，而手头的网线又不够用，该怎么办？

我们必须凭借“拆东墙补西墙”的策略：找到那些“多余”的网线（在一个连通分量内部形成环的线），把它们拔下来，用来连接那些断开的局域网。

这道题的核心在于：如何判断网线“够不够”？以及如果够，大家必须动多少次手？

力扣 1319. 连通网络的处理次数

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

题目分析：

输入：n 台电脑（节点），connections 网线列表（边）。
操作：拔掉一根已有的网线，把它连到另外两台电脑之间。
目标：让所有电脑都连通。求最少操作次数。
特殊情况：如果线缆总数太少，无论怎么移都连不通，返回 -1。

核心洞察：“硬性门槛”与“连通数学”

第一道门槛：资源够不够？ 图论告诉我们：要连通 n 个节点，至少需要 n - 1 条边（这就构成了一棵生成树）。

如果 connections.size() < n - 1：线缆总数根本不够，神仙难救，直接返回 -1。
如果 connections.size() >= n - 1：线缆总数足够！既然总数够，我们一定能通过“拆除冗余、填补空缺”的方式，把图变成连通的。

第二道门槛：需要动几次手？ 假设我们用并查集处理完所有的现有连接后，发现网络中还剩下 k 个互不相通的连通分量（孤岛）。要把这 k 个孤岛连成一个整体，我们需要搭几座桥？很简单，把 k 个点串起来，需要 k - 1 条线。

结论：只要总线缆数达标，我们只得计算出当前的连通分量个数 count，答案就是 count - 1。我们不需要关心具体拔哪根线，缘于题目只问“次数”。

算法流程：并查集的标准作业

硬性检查：如果 connections.size() < n - 1，返回 -1。
初始化并查集：
- parent 数组，大小为 n。
- 关键：初始化连通分量计数器 componentCount = n（一开始大家都是孤岛）。
遍历连接：
- 对于每一条边 [u, v]，调用 union(u, v)。
- 在 union 函数内部：如果 u 和 v 原本不属于同一个集合（rootU != rootV），合并它们，并将 componentCount减 1。
计算结果：
- 遍历结束后，componentCount 就是剩下的连通分量个数。
- 需要的操作次数 = componentCount - 1。

代码完成 (并查集模板应用)

C++

#include 
#include 
using namespace std;
class Solution {
private:// --- 并查集内部类 ---class UnionFind {private:vector parent;int count; // 连通分量个数public:UnionFind(int n) {count = n;parent.resize(n);iota(parent.begin(), parent.end(), 0); // 初始化 0, 1, 2...}int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}void unite(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {parent[rootX] = rootY;count--; // 每次成功合并，孤岛少一个}}int getCount() const {return count;}};
public:int makeConnected(int n, vector>& connections) {// 1. 硬性门槛检查：线缆总数是否足够if (connections.size() < n - 1) {return -1;}// 2. 初始化并查集UnionFind uf(n);// 3. 建立现有的连接for (const auto& conn : connections) {uf.unite(conn[0], conn[1]);}// 4. 计算需要的操作数// 剩下的连通分量个数 - 1，就是连接它们所需的边数return uf.getCount() - 1;}
};

深度复杂度分析

V (Vertices)：电脑数 n。
E (Edges)：线缆数 connections.size()。
时间复杂度 O(n + E * α(n))：
- 初始化并查集得 O(n)。
- 遍历 E 条边进行合并，每次操作近似 O(1)（阿克曼反函数）。
- 总时间近似线性。
空间复杂度 O(n)：
- 并查集的 parent 数组。