2024-02-07：用go语言，一个公司准备组织一场会议，邀请名单上有 n 位员工，
公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工，
员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，
每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议，
每位员工喜欢的员工 不会 是他自己。
给你一个下标从 0 开始的整数数组 favorite，
其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目。
输入：favorite = [2,2,1,2]。
输出：3。
答案2024-02-07：
来自左程云。
灵捷3.5
大体步骤如下：
1.创建一个名为 maximumInvitations 的函数，接受一个整数数组 favorite 作为参数。函数返回值为最多能参加会议的员工数目。
2.在 maximumInvitations 函数中，首先调用 beLoved 函数生成一个被喜欢表，表示每个员工喜欢的员工。
3.调用 calculateDegree 函数计算每个员工的入度，即喜欢该员工的员工数目。
4.初始化一个队列 queue，利用队列进行拓扑排序。
5.将所有入度为 0 的员工加入队列 queue。
6.使用 zeroVisited 数组记录已经访问过的员工。
7.当队列不为空时，从队列中取出一个员工，并标记为已访问。
8.遍历该员工喜欢的员工列表，将其入度减一，若入度减为 0，则将该员工添加到队列中。
9.使用 cycleVisited 数组记录已经访问过的员工，同时统计环上的员工数目。
10.如果某个员工的喜欢的员工也喜欢自己，则说明存在一个长度为 2 的环，更新 arrangeTwoCycle 变量。
11.否则，遍历环上的员工，找到最长的环，更新 arrangeMoreCycle 变量。
12.比较 arrangeTwoCycle 和 arrangeMoreCycle 的值，取较大值作为最终结果。
13.返回最终结果。
总的时间复杂度和额外空间复杂度分别如下：
- • 时间复杂度：O(n^2)，其中 n 是员工数目。遍历每个员工需要 O(n) 的时间，同时查找和更新相关信息的操作也可能需要 O(n) 的时间。
- • 空间复杂度：O(n)，需要额外的空间来存储喜欢关系、度数、访问状态等信息。
go完整代码如下：
代码语言：javascript复制package main
import "fmt"
func maximumInvitations(favorite []int) int {
loved := beLoved(favorite)
degree := calculateDegree(loved)
n := len(favorite)
queue := make([]int, n)
l := 0
r := 0
for i := 0; i < n; i {
if degree[i] == 0 {
queue[r] = i
r
}
}
zeroVisited := make([]bool, n)
for l < r {
cur := queue[l]
l
zeroVisited[cur] = true
if degree[favorite[cur]]--; degree[favorite[cur]] == 0 {
queue[r] = favorite[cur]
r
}
}
cycleVisited := make([]bool, n)
arrangeTwoCycle := 0
arrangeMoreCycle := 0
for i := 0; i < n; i {
if !zeroVisited[i] && !cycleVisited[i] {
cycleVisited[i] = true
if favorite[favorite[i]] == i {
cycleVisited[favorite[i]] = true
arrangeTwoCycle = maxFollow(i, zeroVisited, loved) maxFollow(favorite[i], zeroVisited, loved)
} else {
cur := favorite[i]
curAns := 1
for cur != i {
cycleVisited[cur] = true
curAns
cur = favorite[cur]
}
if curAns > arrangeMoreCycle {
arrangeMoreCycle = curAns
}
}
}
}
if arrangeTwoCycle > arrangeMoreCycle {
return arrangeTwoCycle
}
return arrangeMoreCycle
}
// 生成被喜欢表
func beLoved(favorite []int) [][]int {
n := len(favorite)
size := make([]int, n)
for _, love := range favorite {
size[love]
}
loved := make([][]int, n)
for i := 0; i < n; i {
loved[i] = make([]int, size[i])
}
for i, f := range favorite {
size[f]--
loved[f][size[f]] = i
}
return loved
}
// 求每个点的入度
func calculateDegree(loved [][]int) []int {
n := len(loved)
degree := make([]int, n)
for i := 0; i < n; i {
degree[i] = len(loved[i])
}
return degree
}
// cur不在环上的追随者链条最大长度
func maxFollow(cur int, zeroed []bool, from [][]int) int {
if len(from[cur]) == 0 {
return 1
}
ans := 0
for _, pre := range from[cur] {
if zeroed[pre] {
follow := maxFollow(pre, zeroed, from)
if follow > ans {
ans = follow
}
}
}
return ans 1
}
func main() {
favorite := []int{1, 2, 0}
result := maximumInvitations(favorite)
fmt.Println(result)
}
