1319. 连通网络的操作次数

题目描述:

用以太网线缆将 n 台计算机连接成一个网络,计算机的编号从 0 到 n-1。线缆用 connections 表示,其中 connections[i] = [a, b] 连接了计算机 a 和 b

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections,你可以拔开任意两台直连计算机之间的线缆,并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能,则返回 -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

示例 3:

输入:n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出:-1
解释:线缆数量不足。

示例 4:

输入:n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出:0

提示:

  • 1 <= n <= 10^5
  • 1 <= connections.length <= min(n*(n-1)/2, 10^5)
  • connections[i].length == 2
  • 0 <= connections[i][0], connections[i][1] < n
  • connections[i][0] != connections[i][1]
  • 没有重复的连接。
  • 两台计算机不会通过多条线缆连接。

解题分析及思路:

方法:并查集

思路:

n台计算机中,需要至少n-1条线缆才能连接所有计算机,所以可以分为两种情况:

  1. 如果线缆数量小于n-1,则所有计算机不能全部连接,返回-1
  2. 如果线缆数量大于等于n-1,则所有计算机都可以全部连接,此时需要求出所有的网络数量,并返回网络数量减去1

而网络连接问题可以通过并查集来解决,利用并查集,将计算机分为不同的网络,并统计网络数量。

func makeConnected(n int, connections [][]int) int {
	if len(connections) < n-1 {
		return -1
	}
	parent := make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	var union func(int, int)
	union = func(x, y int) {
		parent[find(x)] = find(y)
	}
	for _, conn := range connections {
		union(conn[0], conn[1])
	}
	var count int
	for i := 0; i < n; i++ {
		if parent[i] == i {
			count++
		}
	}
	return count - 1
}

复杂度:

  • 时间复杂度:O(m * 𝛼(n)),其中 m 是数组 connections 的长度,α 是阿克曼函数的反函数。
  • 空间复杂度:O(n)

执行结果:

  • 执行耗时:49 ms,击败了45.10% 的Go用户
  • 内存消耗:9.4 MB,击败了66.67% 的Go用户

通过次数 50.8K 提交次数 81.1K 通过率 62.6%

Related Posts

1026. 节点与其祖先之间的最大差值

## 题目描述:给定二叉树的根节点 root,找出存在于 不同 节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)示例 1: ![](/img/leetcode/1026节点与其祖先之间的最大差值/tmp-tre

read more

1038. 从二叉搜索树到更大和树

## 题目描述:给定一个二叉搜索树 root (BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。提醒一下, 二叉搜索树 满足下列约束条件:- 节点的左子树仅包含键 小于 节点键的节点。 - 节点的右子树仅包含键 大于 节点键的节点。 - 左右子树也必须是二叉搜索树。*示例 1:***![](/img/leetcode/

read more

105. 从前序与中序遍历序列构造二叉树

## 题目描述:给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。示例 1: ``` 输入: preorder = [3,9,20,15,7], inorder = [

read more

106. 从中序与后序遍历序列构造二叉树

## 题目描述:给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。示例 1: ``` 输入:inorder = [9,3,15,20,7], postorder

read more

109. 有序链表转换二叉搜索树

## 题目描述:给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。示例 1: ``` 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9

read more

114. 二叉树展开为链表

## 题目描述:给你二叉树的根结点 root ,请你将它展开为一个单链表:- 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。示例 1: ``` 输入:root

read more