2023-06-10：給定一個由 n 個節點組成的網絡，用 n x n 個鄰接矩陣 graph 表示
在節點網絡中，隻有當 graph[i][j] = 1 時，節點 i 能夠直接連接到另一個節點 j。
一些節點 initial 最初被惡意軟件感染。隻要兩個節點直接連接，
且其中至少一個節點受到惡意軟件的感染，那麼兩個節點都將被惡意軟件感染。
這種惡意軟件的傳播將繼續，直到沒有更多的節點可以被這種方式感染。
假設 M(initial) 是在惡意軟件停止傳播之後，整個網絡中感染惡意軟件的最終節點數。
我們可以從 initial 中刪除一個節點，
並完全移除該節點以及從該節點到任何其他節點的任何連接。
請返回移除後能夠使 M(initial) 最小化的節點。
如果有多個節點滿足條件，返回索引 最小的節點 。
initial 中每個整數都不同。
輸出：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]。
輸入：0。
答案2023-06-10：
主要思路如下：
1.建立並查集，將感染惡意軟件的節點標記出來。
2.遍歷節點連接，如果兩個節點都沒有被感染，則在並查集中合並這兩個節點。
3.對於initial中的每個節點，遍歷其能夠直接連接的節點，如果節點未被感染，則將其在並查集中的祖先標記為initial中的該節點，如果該祖先已被標記為其他initial中的節點，則將其標記為-2。
4.統計在同一個initial的所有節點中，連接的總節點數，找出連接數最多的initial節點。
5.返回最小索引的節點。
時間復雜度為$O(n^2)$，其中n是節點數，因為要對每個節點進行遍歷和合並操作，最壞情況下需要$O(n^2)$次遍歷和合並操作。
空間復雜度為O(n)，其中n是節點數，因為需要使用一個並查集數組來存儲節點的父節點，另外還需要使用一個數組來記錄每個節點是否被感染和每個initial節點的連接數量。這些數據占用的空間都是O(n)的。
go完整代碼如下：
package main
import (
"fmt"
"sort"
)
func minMalwareSpread(graph [][]int, initial []int) int {
n := len(graph)
virus := make([]bool, n)
for _, i := range initial {
virus[i] = true
}
uf := NewUnionFind(n)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if graph[i][j] == 1 && !virus[i] && !virus[j] {
uf.Union(i, j)
}
}
}
infect := make([]int, n)
for i := range infect {
infect[i] = -1
}
for _, v := range initial {
for next := 0; next < n; next++ {
if v != next && !virus[next] && graph[v][next] == 1 {
f := uf.Find(next)
if infect[f] == -1 {
infect[f] = v
} else if infect[f] != -2 && infect[f] != v {
infect[f] = -2
}
}
}
}
cnt := make([]int, n)
for i := 0; i < n; i++ {
if infect[i] >= 0 {
cnt[infect[i]] += uf.size[i]
}
}
sort.Ints(initial)
ans := initial[0]
count := cnt[ans]
for _, i := range initial {
if cnt[i] > count {
ans = i
count = cnt[i]
}
}
return ans
}
type UnionFind struct {
father []int
size []int
}
func NewUnionFind(n int) *UnionFind {
father := make([]int, n)
size := make([]int, n)
for i := 0; i < n; i++ {
father[i] = i
size[i] = 1
}
return &UnionFind{father, size}
}
func (uf *UnionFind) Find(i int) int {
help := make([]int, 0)
for i != uf.father[i] {
help = append(help, i)
i = uf.father[i]
}
for _, v := range help {
uf.father[v] = i
}
return i
}
func (uf *UnionFind) Union(i, j int) {
fi, fj := uf.Find(i), uf.Find(j)
if fi != fj {
if uf.size[fi] >= uf.size[fj] {
uf.father[fj] = fi
uf.size[fi] += uf.size[fj]
} else {
uf.father[fi] = fj
uf.size[fj] += uf.size[fi]
}
}
}
func main() {
graph := [][]int{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}
initial := []int{0, 1}
fmt.Println(minMalwareSpread(graph, initial))
}