minimize-malware-spread.go

package problem0924

// 题目的意思是，在 graph 中寻找包含 initial 点的连通区域
// 如果，所有包含 initial 点的连通区域，都不止一个 initial 点
//     返回，initial 中的最小值。
// 如果，存在只包含一个 initial 点的连通区域，
//     找到只包含一个 initial 点且最大的连通区域
//     返回其中 initial 点的值。

func minMalwareSpread(graph [][]int, initial []int) int {
	size := len(graph)

	maxCount := -1
	res := size

	// 记录 initial 中的点，并找到其中的最小值作为 res 备选
	isInitial := [301]bool{}
	for _, n := range initial {
		isInitial[n] = true
		res = min(res, n)
	}

	for candidate := 0; candidate < size; candidate++ {
		if !isInitial[candidate] {
			continue
		}

		// 从 initial 中的点，可以寻找连通区域

		queue := make([]int, 1, size)
		queue[0] = candidate

		hasSeen := [301]bool{}
		hasSeen[candidate] = true
		isUnique := true // 标记此连通区域中，只有一个 initial 点
		count := 1       // 记录此连通区域中点的数目

		// BFS
		for len(queue) > 0 {
			queueSize := len(queue)
			for idx := 0; idx < queueSize; idx++ {
				i := queue[idx]
				for j := 0; j < size; j++ {
					if !hasSeen[j] && graph[i][j] == 1 {
						hasSeen[j] = true
						count++
						queue = append(queue, j)
						if isInitial[j] {
							isUnique = false
							isInitial[j] = false
							// 这样就不会再次搜索此连通区域，可以加快速度
							// 并且可以保证 i 就是此连通区域中最小的 initial 点
						}
					}
				}
			}
			queue = queue[queueSize:]
		}

		if isUnique && // 只有一个 initial 点时，才有必要更新 res
			maxCount < count {
			maxCount = count
			res = candidate
		}
	}

	return res
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}