LeetCode 1319. 连通网络的操作次数
字数 2718 2025-12-06 11:28:35

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

题目描述

有 n 台计算机，编号从 0 到 n-1，通过网线连接。给你一个数组 connections，其中 connections[i] = [a, b] 表示计算机 a 和 b 之间有一根网线连接。

网络中的任何计算机都可以通过网络（直接或间接地）访问其他任意计算机。

你的任务是计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1。

一次操作是指：拔掉一台计算机上连接着的某一根网线，并将其插到另一台计算机（或者同一台计算机的其他空闲端口）上。

通俗解释：想象有 n 台电脑，已经有一些网线把它们连了起来。你可以进行一种操作：把一根已经连接两台电脑的网线拔下来，重新接到另一台（或同一台）电脑上。问最少操作多少次，能让所有电脑都连成一个整体网络（即从任何一台电脑都能到达另一台）？如果网线不够，无法实现，就返回 -1。

解题过程循序渐进讲解

第一步：问题转化与初步分析

  1. 核心概念 - 连通分量：在图中，一个“连通分量”是指其中任意两个节点都可以通过路径相互到达的最大子图。我们的目标是把整个网络变成一个连通分量。
  2. 操作的本质：拔下一根网线，等于暂时断开它连接的两个节点在当前连通分量内的连接。把它接到两个不同的连通分量之间，等于用这根线把两个原本独立的连通分量合并了。所以，一次有效的操作可以减少一个连通分量的数量。
  3. 必要条件的判断：要把 n 个节点连成一个连通分量，至少需要 n-1 条边（这是树的结构）。给定的网线数量就是边数 len(connections)。如果 len(connections) < n-1，那么无论如何网线都不够用，直接返回 -1。

第二步：计算初始连通分量数量

  1. 目标：统计在初始布线情况下，网络被分成了几个独立的“连通块”（连通分量）。
  2. 方法：使用并查集 (Union-Find) 是最高效的方法。并查集可以高效地处理“合并集合”和“查询两个元素是否属于同一集合”的操作。
  3. 具体步骤：
    • 初始化一个并查集，包含 n 个节点（0 到 n-1），每个节点初始时自成一个集合。
    • 遍历 connections 数组，对每一对 [a, b]，在并查集中将 a 和 b 所在的集合进行合并（Union操作）。如果它们本来就在一个集合，这次连接就是多余的边（但不影响结果）。
    • 遍历结束后，统计并查集中独立集合（连通分量）的数量。如何统计？可以遍历每个节点 i，找到它的“根节点”（Find操作），根节点相同的节点属于同一个集合。统计不同根节点的个数，就是连通分量的数量，记作 count。

第三步：计算最少操作次数

  1. 关键推导：假设初始有 count 个连通分量。我们的目标是将它们合并成 1 个。
  2. 需要多少连接？ 将 count 个连通分量连接成 1 个，最少需要 count - 1 条边。这就像一个森林（多个树）要变成一棵树，需要在树与树之间添加边。
  3. 边从哪里来？ 从“多余的”网线中来。在初始布线时，连接同一个连通分量内部两个节点的边，对于“将所有分量连通”这个最终目标来说是“多余”的。因为它没有起到连接两个独立分量的作用。在第二步构建并查集时，如果发现 a 和 b 的根节点已经相同，那么这条边就是一条“多余”的边，它为我们提供了一次“操作”的机会（我们可以拔掉它，去连接其他分量）。
  4. 最少操作次数：我们需要 count - 1 条边来连接所有分量。如果“多余”的边数大于等于 count - 1，那么我们只需要 count - 1 次操作（每次用一条多余边连接两个分量）。如果“多余”的边数不够，那在第一步其实就已经因为总边数不足而返回-1了。
  5. 简洁的结论：最少操作次数就是 (连通分量数量) - 1。
    • 因为总边数 >= n-1 保证了有足够的边（或者说，有多余的边）来执行这 count-1 次连接操作。

第四步：算法步骤总结

  1. 边界检查：如果 len(connections) < n - 1，返回 -1。
  2. 初始化并查集：创建一个大小为 n 的并查集结构。
  3. 合并操作：遍历所有连接 connections，对每个 [a, b] 执行并查集的合并（union(a, b)）。在这个过程中，我们可以不显式统计“多余边”数量，因为我们最终只关心连通分量数。
  4. 统计连通分量数：
    • 方法一：在并查集内部维护一个 componentCount 变量，初始为 n。每次成功合并两个不同集合时，将该计数减1。遍历结束后，componentCount 就是连通分量数量。
    • 方法二：遍历所有节点 0 到 n-1，对每个节点找其根节点，用一个集合（Set）来存储所有不重复的根节点。集合的大小就是连通分量数 count。
  5. 计算结果：最少操作次数 = count - 1。

第五步：举例说明

  • 输入：n = 4, connections = [[0,1], [0,2], [1,2]]
  • 步骤：
    1. 检查边数：3 >= 4-1，满足条件。
    2. 初始化并查集：{0}, {1}, {2}, {3}。
    3. 合并：
      • [0,1]: 合并 {0} 和 {1} -> {0,1}, {2}, {3}
      • [0,2]: 合并 {0,1} 和 {2} -> {0,1,2}, {3}
      • [1,2]: 1和2的根节点已相同，这条是多余边，不改变集合。
    4. 统计连通分量：共有 {0,1,2} 和 {3} 两个分量，count = 2。
    5. 计算：2 - 1 = 1。需要一次操作，比如把 [1,2] 这根多余的线拔下来，接到计算机 2 和 3 之间（或 0 和 3 之间等）。
  • 输入：n = 6, connections = [[0,1], [0,2], [0,3], [1,2], [1,3]]
  • 步骤：
    1. 检查边数：5 >= 6-1，满足条件。
    2. 初始化并查集：6个独立集合。
    3. 合并：所有边都在连接 0,1,2,3 这四台机器，最终这4台在一个集合，机器4和5各自独立。
    4. 连通分量数 count = 3 (集合A={0,1,2,3}, 集合B={4}, 集合C={5})。
    5. 最少操作次数 = 3 - 1 = 2。我们需要用2条“多余”的边（比如来自初始连接内部的边）来连接 {4} 和 {5} 到主集合上。
LeetCode 1319. 连通网络的操作次数 题目描述 有 n 台计算机，编号从 0 到 n-1 ，通过网线连接。给你一个数组 connections ，其中 connections[i] = [a, b] 表示计算机 a 和 b 之间有一根网线连接。 网络中的任何计算机都可以通过网络（直接或间接地）访问其他任意计算机。 你的任务是计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。 一次操作是指：拔掉一台计算机上连接着的某一根网线，并将其插到另一台计算机（或者同一台计算机的其他空闲端口）上。 通俗解释 ：想象有 n 台电脑，已经有一些网线把它们连了起来。你可以进行一种操作：把一根已经连接两台电脑的网线拔下来，重新接到另一台（或同一台）电脑上。问最少操作多少次，能让所有电脑都连成一个整体网络（即从任何一台电脑都能到达另一台）？如果网线不够，无法实现，就返回 -1 。 解题过程循序渐进讲解 第一步：问题转化与初步分析 核心概念 - 连通分量 ：在图中，一个“连通分量”是指其中任意两个节点都可以通过路径相互到达的最大子图。我们的目标是把整个网络变成 一个 连通分量。 操作的本质 ：拔下一根网线，等于暂时断开它连接的两个节点在当前连通分量内的连接。把它接到两个不同的连通分量之间，等于用这根线把两个原本独立的连通分量合并了。所以， 一次有效的操作可以减少一个连通分量的数量 。 必要条件的判断 ：要把 n 个节点连成一个连通分量，至少需要 n-1 条边（这是树的结构）。给定的网线数量就是边数 len(connections) 。如果 len(connections) < n-1 ，那么无论如何网线都不够用，直接返回 -1 。 第二步：计算初始连通分量数量 目标 ：统计在初始布线情况下，网络被分成了几个独立的“连通块”（连通分量）。 方法 ：使用 并查集 (Union-Find) 是最高效的方法。并查集可以高效地处理“合并集合”和“查询两个元素是否属于同一集合”的操作。 具体步骤 ： 初始化一个并查集，包含 n 个节点（0 到 n-1），每个节点初始时自成一个集合。 遍历 connections 数组，对每一对 [a, b] ，在并查集中将 a 和 b 所在的集合进行合并（Union操作）。如果它们本来就在一个集合，这次连接就是多余的边（但不影响结果）。 遍历结束后，统计并查集中 独立集合（连通分量）的数量 。如何统计？可以遍历每个节点 i ，找到它的“根节点”（Find操作），根节点相同的节点属于同一个集合。统计不同根节点的个数，就是连通分量的数量，记作 count 。 第三步：计算最少操作次数 关键推导 ：假设初始有 count 个连通分量。我们的目标是将它们合并成 1 个。 需要多少连接？ 将 count 个连通分量连接成 1 个，最少需要 count - 1 条边。这就像一个森林（多个树）要变成一棵树，需要在树与树之间添加边。 边从哪里来？ 从“多余的”网线中来。在初始布线时，连接同一个连通分量内部两个节点的边，对于“将所有分量连通”这个最终目标来说是“多余”的。因为它没有起到连接两个独立分量的作用。在第二步构建并查集时，如果发现 a 和 b 的根节点已经相同，那么这条边就是一条“多余”的边，它为我们提供了一次“操作”的机会（我们可以拔掉它，去连接其他分量）。 最少操作次数 ：我们需要 count - 1 条边来连接所有分量。如果“多余”的边数大于等于 count - 1 ，那么我们只需要 count - 1 次操作（每次用一条多余边连接两个分量）。如果“多余”的边数不够，那在第一步其实就已经因为总边数不足而返回-1了。 简洁的结论 ：最少操作次数就是 (连通分量数量) - 1 。 因为总边数 >= n-1 保证了有足够的边（或者说，有多余的边）来执行这 count-1 次连接操作。 第四步：算法步骤总结 边界检查 ：如果 len(connections) < n - 1 ，返回 -1 。 初始化并查集 ：创建一个大小为 n 的并查集结构。 合并操作 ：遍历所有连接 connections ，对每个 [a, b] 执行并查集的合并（ union(a, b) ）。在这个过程中，我们可以不显式统计“多余边”数量，因为我们最终只关心连通分量数。 统计连通分量数 ： 方法一：在并查集内部维护一个 componentCount 变量，初始为 n 。每次成功合并两个不同集合时，将该计数减1。遍历结束后， componentCount 就是连通分量数量。 方法二：遍历所有节点 0 到 n-1 ，对每个节点找其根节点，用一个集合（Set）来存储所有不重复的根节点。集合的大小就是连通分量数 count 。 计算结果 ：最少操作次数 = count - 1 。 第五步：举例说明 输入 ： n = 4 , connections = [[0,1], [0,2], [1,2]] 步骤 ： 检查边数： 3 >= 4-1 ，满足条件。 初始化并查集：{0}, {1}, {2}, {3}。 合并： [0,1] : 合并 {0} 和 {1} -> {0,1}, {2}, {3} [0,2] : 合并 {0,1} 和 {2} -> {0,1,2}, {3} [1,2] : 1和2的根节点已相同，这条是多余边，不改变集合。 统计连通分量：共有 {0,1,2} 和 {3} 两个分量， count = 2 。 计算： 2 - 1 = 1 。需要一次操作，比如把 [1,2] 这根多余的线拔下来，接到计算机 2 和 3 之间（或 0 和 3 之间等）。 输入 ： n = 6 , connections = [[0,1], [0,2], [0,3], [1,2], [1,3]] 步骤 ： 检查边数： 5 >= 6-1 ，满足条件。 初始化并查集：6个独立集合。 合并：所有边都在连接 0,1,2,3 这四台机器，最终这4台在一个集合，机器4和5各自独立。 连通分量数 count = 3 (集合A={0,1,2,3}, 集合B={4}, 集合C={5})。 最少操作次数 = 3 - 1 = 2 。我们需要用2条“多余”的边（比如来自初始连接内部的边）来连接 {4} 和 {5} 到主集合上。