昨天的
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
}

別卷了