1319. 连通网络的操作次数
题目描述
有 n 台计算机，编号从 0 到 n - 1。输入数组 connections，connections[i] = [a, b] 表示有一根网线直接连着 a 和 b。通过网线直接或间接相连的计算机可以互相访问。
每次操作可以拔下一根已有的网线，改接到两台原本没有直接相连的计算机之间。
返回让所有计算机都能互相访问所需的最少操作次数。如果网线总数不够，无论怎么接都做不到，返回 -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
解释：4 和 5 各自孤立，有两根多余的网线可以改接，正好需要 2 次。
示例 3
输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]] 输出：-1
解释：6 台计算机至少需要 5 根网线，这里只有 4 根。
数据范围
1 <= n <= 10^51 <= connections.length <= min(n*(n-1)/2, 10^5)connections[i].length == 20 <= connections[i][0], connections[i][1] < nconnections[i][0] != connections[i][1]- 没有重复的连接。
- 任意两台计算机之间最多只有一根网线。
解题思路：并查集统计连通分量
连通 n 台机器至少需要 n-1 根线，不够直接返回 -1。线够的话，答案就是“连通块数 − 1”：每次拿一根多余的线（在同一块内成环的线）去连两个块。用并查集遍历所有线，每合并一次块数减 1。
为什么正确
处理完前 t 根线后，parts 等于只用这 t 根线时的连通块数。
复杂度分析
带路径压缩的并查集，时间近似 O(n + E)，空间 O(n)。
易错点
不要去数“多余的线”和块数比较；先判断 E ≥ n-1，就保证多余的线一定够用。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
if len(connections) < n - 1:
return -1
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
parts = n
for a, b in connections:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
parts -= 1
return parts - 1class Solution {
private int[] parent;
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) {
return -1;
}
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int parts = n;
for (int[] c : connections) {
int ra = find(c[0]), rb = find(c[1]);
if (ra != rb) {
parent[ra] = rb;
parts--;
}
}
return parts - 1;
}
}class Solution {
vector<int> parent;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if ((int)connections.size() < n - 1) {
return -1;
}
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
int parts = n;
for (auto& c : connections) {
int ra = find(c[0]), rb = find(c[1]);
if (ra != rb) {
parent[ra] = rb;
parts--;
}
}
return parts - 1;
}
};func makeConnected(n int, connections [][]int) int {
if len(connections) < n-1 {
return -1
}
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
find := func(x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
parts := n
for _, c := range connections {
ra, rb := find(c[0]), find(c[1])
if ra != rb {
parent[ra] = rb
parts--
}
}
return parts - 1
}var makeConnected = function(n, connections) {
if (connections.length < n - 1) {
return -1;
}
const parent = Array.from({ length: n }, (_, i) => i);
const find = x => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let parts = n;
for (const [a, b] of connections) {
const ra = find(a), rb = find(b);
if (ra !== rb) {
parent[ra] = rb;
parts--;
}
}
return parts - 1;
};function makeConnected(n: number, connections: number[][]): number {
if (connections.length < n - 1) {
return -1;
}
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let parts = n;
for (const [a, b] of connections) {
const ra = find(a), rb = find(b);
if (ra !== rb) {
parent[ra] = rb;
parts--;
}
}
return parts - 1;
}其他解法
两种方法都在统计连通分量个数。并查集逐条处理边，适合边动态加入的场景；DFS 需要先建好整张图再遍历，思路最直观。
解法 2：深度优先搜索统计连通分量 时间 O(n + m)，空间 O(n + m)
先判断线缆数是否至少为 n − 1，不够就一定连不通。线缆够用时，每条多余的线都能拆下来连接两个分量，所以答案只取决于连通分量的个数 k，等于 k − 1。用邻接表建图，从每个还没访问过的电脑出发做一次深度优先搜索，把能到达的电脑全部标记，搜索的次数就是连通分量个数。
图的遍历最直观，不需要理解并查集的路径压缩和合并。需要先建邻接表，占用 O(n + m) 额外空间；并查集只要一个父数组，而且能边读边合并。
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
if len(connections) < n - 1:
return -1
adj = [[] for _ in range(n)]
for a, b in connections:
adj[a].append(b)
adj[b].append(a)
seen = [False] * n
parts = 0
for start in range(n):
if seen[start]:
continue
parts += 1
seen[start] = True
stack = [start]
while stack:
u = stack.pop()
for v in adj[u]:
if not seen[v]:
seen[v] = True
stack.append(v)
return parts - 1class Solution {
public int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) return -1;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : connections) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
boolean[] seen = new boolean[n];
int parts = 0;
for (int start = 0; start < n; start++) {
if (seen[start]) continue;
parts++;
seen[start] = true;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int u = stack.pop();
for (int v : adj.get(u)) {
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
}
}
return parts - 1;
}
}class Solution {
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if ((int)connections.size() < n - 1) return -1;
vector<vector<int>> adj(n);
for (auto& e : connections) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
vector<bool> seen(n, false);
int parts = 0;
for (int start = 0; start < n; start++) {
if (seen[start]) continue;
parts++;
seen[start] = true;
vector<int> stk = {start};
while (!stk.empty()) {
int u = stk.back();
stk.pop_back();
for (int v : adj[u]) {
if (!seen[v]) {
seen[v] = true;
stk.push_back(v);
}
}
}
}
return parts - 1;
}
};func makeConnected(n int, connections [][]int) int {
if len(connections) < n-1 {
return -1
}
adj := make([][]int, n)
for _, e := range connections {
adj[e[0]] = append(adj[e[0]], e[1])
adj[e[1]] = append(adj[e[1]], e[0])
}
seen := make([]bool, n)
parts := 0
for start := 0; start < n; start++ {
if seen[start] {
continue
}
parts++
seen[start] = true
stack := []int{start}
for len(stack) > 0 {
u := stack[len(stack)-1]
stack = stack[:len(stack)-1]
for _, v := range adj[u] {
if !seen[v] {
seen[v] = true
stack = append(stack, v)
}
}
}
}
return parts - 1
}var makeConnected = function(n, connections) {
if (connections.length < n - 1) return -1;
const adj = Array.from({ length: n }, () => []);
for (const [a, b] of connections) {
adj[a].push(b);
adj[b].push(a);
}
const seen = new Array(n).fill(false);
let parts = 0;
for (let start = 0; start < n; start++) {
if (seen[start]) continue;
parts++;
seen[start] = true;
const stack = [start];
while (stack.length) {
const u = stack.pop();
for (const v of adj[u]) {
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
}
}
return parts - 1;
};function makeConnected(n: number, connections: number[][]): number {
if (connections.length < n - 1) return -1;
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of connections) {
adj[a].push(b);
adj[b].push(a);
}
const seen: boolean[] = new Array(n).fill(false);
let parts = 0;
for (let start = 0; start < n; start++) {
if (seen[start]) continue;
parts++;
seen[start] = true;
const stack = [start];
while (stack.length) {
const u = stack.pop()!;
for (const v of adj[u]) {
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
}
}
return parts - 1;
}