1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| // @Title: 项目管理 (Sort Items by Groups Respecting Dependencies)
// @Author: 15816537946@163.com
// @Date: 2021-01-12 23:32:08
// @Runtime: 72 ms
// @Memory: 17.5 MB
func topSort(graph [][]int, deg, items []int) (orders []int) {
q := []int{}
for _, i := range items {
if deg[i] == 0 {
q = append(q, i)
}
}
for len(q) > 0 {
from := q[0]
q = q[1:]
orders = append(orders, from)
for _, to := range graph[from] {
deg[to]--
if deg[to] == 0 {
q = append(q, to)
}
}
}
return
}
func sortItems(n, m int, group []int, beforeItems [][]int) (ans []int) {
groupItems := make([][]int, m+n) // groupItems[i] 表示第 i 个组负责的项目列表
for i := range group {
if group[i] == -1 {
group[i] = m + i // 给不属于任何组的项目分配一个组
}
groupItems[group[i]] = append(groupItems[group[i]], i)
}
groupGraph := make([][]int, m+n) // 组间依赖关系
groupDegree := make([]int, m+n)
itemGraph := make([][]int, n) // 组内依赖关系
itemDegree := make([]int, n)
for cur, items := range beforeItems {
curGroupID := group[cur]
for _, pre := range items {
preGroupID := group[pre]
if preGroupID != curGroupID { // 不同组项目,确定组间依赖关系
groupGraph[preGroupID] = append(groupGraph[preGroupID], curGroupID)
groupDegree[curGroupID]++
} else { // 同组项目,确定组内依赖关系
itemGraph[pre] = append(itemGraph[pre], cur)
itemDegree[cur]++
}
}
}
// 组间拓扑序
items := make([]int, m+n)
for i := range items {
items[i] = i
}
groupOrders := topSort(groupGraph, groupDegree, items)
if len(groupOrders) < len(items) {
return nil
}
// 按照组间的拓扑序,依次求得各个组的组内拓扑序,构成答案
for _, groupID := range groupOrders {
items := groupItems[groupID]
orders := topSort(itemGraph, itemDegree, items)
if len(orders) < len(items) {
return nil
}
ans = append(ans, orders...)
}
return
}
|