要过年了
我怎么还在写每日，一定有哪里搞错了
2127. Maximum Employees to Be Invited to a Meeting
思路：
就是去找最长cycle的长度
又可以依照cycle长度分成两种情况
1.长度 > 2
就单纯纪录cycle的长度就好
2.长度 = 2
这个比较麻烦一点
假设是i、j形成cycle
那你要记录到i最长的长度 + 到j最长的长度才会是可以围成圆桌的人数
接着每一个cycle长度 = 2的圆桌可以合并相加起来
就照上述两种情况去处理就好
golang code :
type node_info struct {
depth int //该node(包含)以前有几个node
length int //该node(包含)以后有几个node
end_node int // -1表示还形成cycle　-2表示已经形成cycle，且cycle长度>2　其他表
示cycle长度=2
}
func maximumInvitations(favorite []int) int {
n, ans := len(favorite), 0
var dfs func(node, depth int) int
nodes, visited := make([]node_info, n), make([]bool, n)
for i := 0; i < n; i++ {
nodes[i].end_node = -1
if favorite[favorite[i]] == i {
nodes[i].length = 1
nodes[favorite[i]].length = 1
visited[i], visited[favorite[i]] = true, true
nodes[i].end_node = i
nodes[favorite[i]].end_node = favorite[i]
}
}
dfs = func(node, depth int) int {
visited[node] = true
nodes[node].depth = depth
next_node := favorite[node]
if visited[next_node] {
if nodes[next_node].end_node == -2 {
nodes[node].end_node = -2
return -1
} else if nodes[next_node].end_node == -1 {
nodes[node].end_node = -2
nodes[node].length = 1
ans = max(ans, depth-nodes[next_node].depth+1)
return 1
} else {
end_node := nodes[next_node].end_node
if end_node == next_node {
if depth+1 > nodes[end_node].length {
nodes[end_node].length = depth + 1
}
nodes[node].length = 2
} else {
if nodes[end_node].length < depth+nodes[next_node].length {
nodes[end_node].length = depth + nodes[next_node].length
}
nodes[node].length = nodes[next_node].length + 1
}
nodes[node].end_node = end_node
return nodes[node].length
}
} else {
length := dfs(next_node, depth+1)
nodes[node].length = length + 1
nodes[node].end_node = nodes[next_node].end_node
return nodes[node].length
}
}
for i := 0; i < n; i++ {
if !visited[i] {
dfs(i, 1)
}
}
tmp := 0
for i := 0; i < n; i++ {
nodes[i].end_node = -1
if favorite[favorite[i]] == i {
tmp += nodes[i].length
}
}
return max(tmp, ans)
}