给你一个整数 n ,表示有 n 个专家从 0 到 n - 1 编号。
另外给一个下标从 0 开始的二维整数数组 meetings ,
其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。
一个专家可以同时参加 多场会议 。最后,给你一个整数 firstPerson 。
专家 0 有一个 秘密 ,最初,他在时间 0 将这个秘密分享给了专家 firstPerson 。
这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是,每次会议,
如果专家 xi 在时间 timei 时知晓这个秘密,那么他将会与专家 yi 分享这个秘密,反之亦然。
秘密共享是 瞬时发生 的。也就是说,在同一时间,一个专家不光可以接收到秘密,还能在其他会议上与其他专家分享。
在所有会议都结束之后,返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。
按开会时间排序。并查集。
代码用golang编写。代码如下:
package main
import (
"fmt"
"sort"
)
func main() {
n := 6
meetings := [][]int{{1, 2, 5}, {2, 3, 8}, {1, 5, 10}}
firstPerson := 1
ret := findAllPeople(n, meetings, firstPerson)
fmt.Println(ret)
}
func findAllPeople(n int, meetings [][]int, firstPerson int) []int {
// 0~n-1号专家,各自建立小集合
// (0, firstPerson)合在一起,作为知道秘密的集合
uf := NewUnionFind(n, firstPerson)
m := len(meetings)
sort.Slice(meetings, func(i, j int) bool {
a := meetings[i]
b := meetings[j]
return a[2] < b[2]
})
// [1,7,1] [2,4,2] [3,6,2]
// 1,7 2,4 3,6
help := make([]int, m<<1)
help[0] = meetings[0][0]
help[1] = meetings[0][1]
size := 2
for i := 1; i < m; i++ {
// i 2
if meetings[i][2] != meetings[i-1][2] {
share(help, size, uf)
help[0] = meetings[i][0]
help[1] = meetings[i][1]
size = 2
} else {
help[size] = meetings[i][0]
size++
help[size] = meetings[i][1]
size++
}
}
share(help, size, uf)
ans := make([]int, 0)
for i := 0; i < n; i++ {
if uf.know(i) {
ans = append(ans, i)
}
}
return ans
}
func share(help []int, size int, uf *UnionFind) {
for i := 0; i < size; i += 2 {
uf.union(help[i], help[i+1])
}
for i := 0; i < size; i++ {
if !uf.know(help[i]) {
uf.isolate(help[i])
}
}
}
type UnionFind struct {
father []int
sect []bool
help []int
}
func NewUnionFind(n, first int) *UnionFind {
ans := &UnionFind{}
ans.father = make([]int, n)
ans.sect = make([]bool, n)
ans.help = make([]int, n)
for i := 1; i < n; i++ {
ans.father[i] = i
}
ans.father[first] = 0
ans.sect[0] = true
return ans
}
func (this *UnionFind) find(i int) int {
hi := 0
for i != this.father[i] {
this.help[hi] = i
hi++
i = this.father[i]
}
for hi--; hi >= 0; hi-- {
this.father[this.help[hi]] = i
}
return i
}
func (this *UnionFind) union(i, j int) {
fatheri := this.find(i)
fatherj := this.find(j)
if fatheri != fatherj {
this.father[fatherj] = fatheri
this.sect[fatheri] = this.sect[fatheri] || this.sect[fatherj]
}
}
func (this *UnionFind) know(i int) bool {
return this.sect[this.find(i)]
}
func (this *UnionFind) isolate(i int) {
this.father[i] = i
}
执行结果如下: