目录
题目描述
There are n computers numbered from 0 to n-1 connected by ethernet cables connections forming a network where connections[i] = [a, b] represents a connection between computers a and b. Any computer can reach any other computer directly or indirectly through the network.
Given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it’s not possible, return -1.
Example 1:
Input：n = 4, connections = [[0,1],[0,2],[1,2]]
Output：1
Explanation：Remove cable between computer 1 and 2 and place between computers 1 and 3.
Example 2:
Input：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output：2
Example 3:
Input：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output：-1
Explanation：There are not enough cables.
Example 4:
Input：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
Output：0
Constraints:
- 1 <= n <= 1 0 5 10^5 105
- 1 <= connections.length <= min(n*(n-1)/2, 1 0 5 10^5 105)
- connections[i].length == 2
- 0 <= connections[i][0], connections[i][1] < n
- connections[i][0] != connections[i][1]
- There are no repeated connections.
- No two computers are connected by more than one cable.
题目来源：https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/
题目大意
目前一共有 n n n台电脑，分别编号为 0 , 1 , ⋯ , n − 1 0,1,\cdots,n - 1 0,1,⋯,n−1，connections数组描述了它们之间的网线连接情况，connections[i] = [a, b]表明编号为 a a a、 b b b的电脑之间有一条网络。为了保证这 n n n台电脑之间是互连的，可以拆开两台电脑之间的网络用于连接其它未连接的电脑，题目问最少需操作多少次，并返回该值；而如果无法使得这 n n n台电脑互连，则返回-1。
解题方法
方法一：并查集
思路
首先要明确的是，要使
n
n
n台电脑之间是互连的，至少需要
n
−
1
n - 1
n−1条网线。因此，如果输入数组connections中的网线数量少于
n
−
1
n - 1
n−1，则说明这些电脑不可能全部互连，应该直接返回-1。除此之外，这道题的思路与547.省份数量几乎是一摸一样的，本质上是让我们求出图中连通块的数量
k
k
k，由于每个连通块中的电脑是互连的，那么只需让这
k
k
k个连通块互连就能让所有电脑都互连了，因此最少操作次数就为
k
−
1
k - 1
k−1。
代码
class Solution {
int[] p;
public int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
public void union(int x, int y){
p[find(x)] = find(y);
}
public int makeConnected(int n, int[][] connections) {
int cablesNum = connections.length;
if(cablesNum < n - 1) return -1;
p = new int[n];
for(int i = 0; i < n ; i ++) p[i] = i;
for(int i = 0; i < cablesNum; i ++) union(connections[i][0], connections[i][1]);
int parts = 0;
for(int i = 0; i < n; i ++){
if(p[i] == i) parts ++;
}
return parts - 1;
}
}
复杂度分析
- 时间复杂度： O ( m l o g n ) O(mlogn) O(mlogn)，其中 m m m为网线数量， n n n为电脑数量。需遍历connections数组中的网线来进行合并，这部分的时间复杂度是 O ( m ) O(m) O(m)，另外，并查集的操作的最坏时间复杂度是 O ( l o g n ) O(logn) O(logn)，因此整体时间复杂度为 O ( m l o g n ) O(mlogn) O(mlogn)。
- 空间复杂度： O ( n ) O(n) O(n)，其中 n n n为电脑数量，需要用数组 p p p来存储每台电脑（或节点）的父节点。