039.并查集-下

前置知识：并查集-上

并查集 §

本节课讲解并查集的更多题目

并查集的小扩展 §

可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息

备注 §

带权并查集的内容是大厂笔试面试冷门内容，会在【挺难】课程里讲述。

可持久化并查集、可撤销并查集，更是比较冷门的内容，备战比赛的同学自行学习，本系列课程不再安排讲述

题目1.移除最多的同行或同列石头 §

题目描述 §

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

提示：

• 1 <= stones.length <= 1000
• 0 <= xi, yi <= 10^4
• 不会有两块石头放在同一个坐标点上

测试链接 §

947.移除最多的同行或同列石头

思路 §

将同列或同行的石头合并，从外往内移除，最后可以移除到只剩一块石头，所以可以移除的石子的最大数量 = 所以石子数量 - 并查集集合数量

因为石头的坐标到 $10^4$，石头的数量到 1000，并查集为了减少空间占用存储石头编号而不是坐标，需要两个哈希表记录每行每列第一个石头的编号

答案 §

const (
	MAXN = 1001
)
 
var (
	// key: 行数
	// value: 该行第一个石头编号
	rowFirst = map[int]int{}
	colFirst = map[int]int{}
 
	father   = [MAXN]int{}
	setCount = 0
)
 
func removeStones(stones [][]int) int {
	n := len(stones)
	build(n)
	for i := 0; i < n; i++ {
		row := stones[i][0]
		col := stones[i][1]
		if no, has := rowFirst[row]; !has {
			// 该行还没有石头，记录一下
			rowFirst[row] = i
		} else {
			// 该行已经有石头了，加入并查集
			union(i, no)
		}
		if no, has := colFirst[col]; !has {
			colFirst[col] = i
		} else {
			union(i, no)
		}
	}
	return n - setCount
}
 
func build(n int) {
	clear(rowFirst)
	clear(colFirst)
	for i := 0; i < n; i++ {
		father[i] = i
	}
	setCount = n
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
func union(a, b int) {
	af := find(a)
	bf := find(b)
	if af == bf {
		return
	}
	father[af] = bf
	setCount--
}

题目2.找出知晓秘密的所有专家 §

题目描述 §

给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。

专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。

秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。

在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。

提示：

• 2 <= n <= 10^5
• 1 <= meetings.length <= 10^5
• meetings[i].length == 3
• 0 <= xi, yi <= n - 1
• xi != yi
• 1 <= timei <= 10^5
• 1 <= firstPerson <= n - 1

测试链接 §

2092.找出知晓秘密的所有专家

答案 §

const (
	MAXN = 1e5 + 1
)
 
var (
	father = [MAXN]int{}
	// 集合的标签信息: 设置集合的一些属性
	// 属性在哪？knew[代表元素] 代表集合的属性
	knew = [MAXN]bool{}
)
 
func findAllPeople(n int, meetings [][]int, firstPerson int) []int {
	// 按会议时间排序
	sort.Slice(meetings, func(a, b int) bool {
		return meetings[a][2] < meetings[b][2]
	})
	m := len(meetings)
	build(n, firstPerson)
	for l, r := 0, 0; l < m; {
		r = l
		for r+1 < m && meetings[l][2] == meetings[r+1][2] {
			r++
		}
		// l...r 这些会议，是一个时刻
		for i := l; i <= r; i++ {
			union(meetings[i][0], meetings[i][1])
		}
		// 有小的撤销行为，但这不是可撤销并查集
		// 只是每一批没有知道秘密的专家重新建立集合而已
		for i := l; i <= r; i++ {
			// 不知道秘密就解散，知道秘密也可以解散
			// 但是知道秘密解不解散不影响答案
			// 为了不运行无用逻辑，就不解散了
			a := meetings[i][0]
			b := meetings[i][1]
			if !knew[find(a)] {
				father[a] = a
			}
			if !knew[find(b)] {
				father[b] = b
			}
		}
		l = r + 1
	}
	ans := []int{}
	for i := 0; i < n; i++ {
		if knew[find(i)] {
			ans = append(ans, i)
		}
	}
	return ans
}
 
func build(n, firstPerson int) {
	for i := 0; i < n; i++ {
		father[i] = i
		knew[i] = false
	}
	// 0 知道秘密，并且告诉了 firstPerson
	knew[0] = true
	father[firstPerson] = 0
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
func union(a, b int) {
	af := find(a)
	bf := find(b)
	if af == bf {
		return
	}
	father[af] = bf
	if knew[af] {
		knew[bf] = true
	}
}

复杂度 §

时间复杂度：

• 排序：$O(m\ast lo{g}^m)$
• 处理过程：$O(m)$
• 收集答案：$O(n)$

空间复杂度：$O(n)$，并查集及并查集标签信息

题目3.好路径的数目 §

题目描述 §

给你一棵 n 个节点的树（连通无向无环的图），节点编号从 0 到 n - 1 且恰好有 n - 1 条边。

给你一个长度为 n 下标从 0 开始的整数数组 vals ，分别表示每个节点的值。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

一条 好路径 需要满足以下条件：

1. 开始节点和结束节点的值 相同 。
2. 开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值（也就是说开始节点的值应该是路径上所有节点的最大值）。

请你返回不同好路径的数目。

注意，一条路径和它反向的路径算作 同一 路径。比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径。

提示：

• n == vals.length
• 1 <= n <= 3 * 104
• 0 <= vals[i] <= 105
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• edges 表示一棵合法的树

测试链接 §

2421.好路径的数目

思路 §

将边按照两个节点较大值进行从小到大排序，遍历边时将两个节点进行合并，如果两个节点所在的集合最大值相同，则说明这两个节点所在的集合有最大值个数乘最大值个数个“好路径”（因为边已经从小到大排序好的）

答案 §

const (
	MAXN = 30001
)
 
var (
	// 需要保证集合中，代表节点的值，一定是整个集合的最大值
	father = [MAXN]int{}
	// 集合中最大值的次数，也就是集合中代表节点的值有几个
	maxCnt = [MAXN]int{}
 
	theVals []int
)
 
func numberOfGoodPaths(vals []int, edges [][]int) int {
	theVals = vals
	n := len(vals)
	build(n)
	// 每个节点自己就是“好路径”
	ans := n
	// 处理边的时候，依次从小节点往大节点处理
	sort.Slice(edges, func(i, j int) bool {
		return max(vals[edges[i][0]], vals[edges[i][1]]) < max(vals[edges[j][0]], vals[edges[j][1]])
	})
	for _, edge := range edges {
		ans += union(edge[0], edge[1])
	}
	return ans
}
 
func build(n int) {
	for i := 0; i < n; i++ {
		father[i] = i
		maxCnt[i] = 1
	}
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
// 核心！
// 谁的值大，谁做代表节点
// 同时注意 maxCnt 的更新
// 返回有几条“好路径”
func union(a, b int) int {
	// a 所在集团的代表节点，同时也是 a 所在集团的最大值下标
	af := find(a)
	// b 所在集团的代表节点，同时也是 b 所在集团的最大值下标
	bf := find(b)
	pathCnt := 0
	if theVals[af] > theVals[bf] {
		father[bf] = af
	} else if theVals[af] < theVals[bf] {
		father[af] = bf
	} else {
		// 两个集团最大值一样
		pathCnt = maxCnt[af] * maxCnt[bf]
		father[af] = bf
		maxCnt[bf] += maxCnt[af]
	}
	return pathCnt
}

复杂度 §

时间复杂度：

• 排序：$O(m\ast lo{g}^m)$，$m$ 为边的数量
• 处理过程：$O(m)$

空间复杂度：$O(m)$，并查集及并查集标签信息

题目4.尽量减少恶意软件的传播 II §

题目描述 §

给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。

请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。

提示：

• n == graph.length
• n == graph[i].length
• 2 <= n <= 300
• graph[i][j] 是 0 或 1.
• graph[i][j] == graph[j][i]
• graph[i][i] == 1
• 1 <= initial.length < n
• 0 <= initial[i] <= n - 1
•  initial 中每个整数都不同

测试链接 §

928.尽量减少恶意软件的传播 II

思路 §

先将所有联通的非病毒源头点合并到同一集合

再遍历病毒源头，将病毒源头周围的普通点（集合）去设置源头！

• 一个源头，可以救，记录病毒源头
• 一个以上源头，无法救（题目要求只能移除一个病毒源头）

最后收集答案：看只有一个源头的集合元素个数，返回最大个数即可，最大个数相同，返回索引较小的

答案 §

const (
	MAXN = 301
)
 
var (
	// initial 数组不好查某个元素是否被感染
	// virus 方便查询
	virus = [MAXN]bool{}
	// 每个源头点删掉的话，能拯救多少点的数据
	cnts = [MAXN]int{}
	// 集合的标签: 集合的感染点是什么点
	// a: 代表点，整个集合源头是 infect[a]
	// infect[a] == -1，目前这个集合没有发现源头
	// infect[a] >= 0，目前这个集合源头是 infect[a]
	// infect[a] == -2，目前这个集合源头不止一个，已经无法拯救了!
	infect = [MAXN]int{}
	father = [MAXN]int{}
	// 集合的标签: 集合的大小是多少
	size = [MAXN]int{}
)
 
func minMalwareSpread(graph [][]int, initial []int) int {
	n := len(graph)
	build(n, initial)
	// 先将所有联通的非病毒源头点合并到同一集合
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			// i, j 有联通，并且 i, j 都不是病毒源头
			if graph[i][j] == 1 && !virus[i] && !virus[j] {
				// 并查集只处理非病毒源头的点
				union(i, j)
			}
		}
	}
 
	// 病毒周围的普通点（集合）去设置源头！
	for _, sick := range initial {
		for neighbor := 0; neighbor < n; neighbor++ {
			// 是普通点，并且与病毒源头联通
			if !virus[neighbor] && graph[sick][neighbor] == 1 {
				nf := find(neighbor)
				if infect[nf] == -1 {
					// 设置成当前源头点
					infect[nf] = sick
				} else if infect[nf] != sick {
					// 设置成多源头点，无法拯救
					infect[nf] = -2
				}
			}
		}
	}
 
	// 统计拯救数据
	for i := 0; i < n; i++ {
		// 是代表点，并且只有一个源头点
		if i == find(i) && infect[i] >= 0 {
			cnts[infect[i]] += size[i]
		}
	}
	sort.Ints(initial) // 拯救数据相同时，返回索引最小，所以按索引升序排列
	ans := initial[0]
	maxx := cnts[ans]
	for _, i := range initial {
		if cnts[i] > maxx {
			ans = i
			maxx = cnts[i]
		}
	}
	return ans
}
 
func build(n int, initial []int) {
	for i := 0; i < n; i++ {
		virus[i] = false
		cnts[i] = 0
		infect[i] = -1
		father[i] = i
		size[i] = 1
	}
	for _, i := range initial {
		virus[i] = true
	}
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
func union(a, b int) {
	af := find(a)
	bf := find(b)
	if af == bf {
		return
	}
	// 本题正好需要 size 数据，顺便就加一下小挂大的优化
	if size[af] < size[bf] {
		father[af] = bf
		size[bf] += size[af]
	} else {
		father[bf] = af
		size[af] += size[bf]
	}
}

复杂度 §

时间复杂度：

• 将所有联通的非病毒源头点合并到同一集合：$O(n^2)$
• 病毒周围的普通点（集合）设置源头：$O(m\ast n)$，$m$ 为病毒源头数
• 统计拯救数据：$O(n+m\ast lo{g}^m)$

空间复杂度：$O(n)$，并查集及并查集标签信息