昨天的
2493. Divide Nodes Into the Maximum Number of Groups
思路:
题目有说不是每个点都有连通
所以可能有好几组graph
总之就把每个graph上的每一点当作root往下走
看哪一点当root可以到达的深度最大，就是这个graph的长度
然后如果这个graph不是bipartite就没办法达到要求，直接回传-1
golang code :
func magnificentSets(n int, edges [][]int) int {
graph, ans := make([][]int, n), 0
for _, edge := range edges {
a, b := edge[0]-1, edge[1]-1
graph[a] = append(graph[a], b)
graph[b] = append(graph[b], a)
}
length := make([]int, n)
for i := 0; i < n; i++ {
q, root, depth, maxdepth := []int{i}, i, make([]int, n), 1
depth[i] = 1
for len(q) > 0 {
node := q[0]
q = q[1:]
root = min(root, node)
for _, next_node := range graph[node] {
if depth[next_node] == 0 {
depth[next_node] = depth[node] + 1
maxdepth = max(maxdepth, depth[next_node])
q = append(q, next_node)
} else if abs(depth[node]-depth[next_node]) != 1 {
return -1
}
}
}
length[root] = max(length[root], maxdepth)
}
for _, val := range length {
ans += val
}
return ans
}
func abs(i int) int {
if i > 0 {
return i
}
return -i
}

别卷了