forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort-items-by-groups-respecting-dependencies.cpp
89 lines (84 loc) · 2.65 KB
/
sort-items-by-groups-respecting-dependencies.cpp
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// Time: O(n + e)
// Space: O(n + e)
class Solution {
public:
vector<int> sortItems(int n, int m, vector<int>& group_id, vector<vector<int>>& beforeItems) {
for (int i = 0; i < n; ++i) {
if (group_id[i] == -1) {
group_id[i] = m++;
}
}
Topo global_group;
for (int i = 0; i < m; ++i) {
global_group.addNode(i);
}
unordered_map<int, Topo> local_groups;
for (int i = 0; i < n; ++i) {
local_groups[group_id[i]].addNode(i);
}
for (int i = 0; i < n; ++i) {
for (const auto& j : beforeItems[i]) {
if (group_id[i] == group_id[j]) {
local_groups[group_id[i]].addEdge(j, i);
} else {
global_group.addEdge(group_id[j], group_id[i]);
}
}
}
vector<int> result;
const auto& global_order = global_group.sort();
if (!global_order) {
return {};
}
for (const auto& i : *global_order) {
const auto& local_order = local_groups[i].sort();
if (!local_order) {
return {};
}
for (const auto& x : *local_order) {
result.emplace_back(x);
}
}
return result;
}
private:
class Topo {
public:
void addNode(int node) {
nodes_.emplace(node);
}
void addEdge(int from, int to) {
addNode(from), addNode(to);
in_degree_[to].emplace(from);
out_degree_[from].emplace(to);
}
unique_ptr<vector<int>> sort() {
queue<int> q;
auto result = make_unique<vector<int>>();
for (const auto& node : nodes_) {
if (!in_degree_.count(node)) {
q.emplace(node);
}
}
while (!q.empty()) {
auto node = q.front(); q.pop();
result->emplace_back(node);
for (const auto& nei : out_degree_[node]) {
in_degree_[nei].erase(node);
if (in_degree_[nei].empty()) {
in_degree_.erase(nei);
q.emplace(nei);
}
}
}
if (result->size() < nodes_.size()) {
return nullptr;
}
return result;
}
private:
unordered_set<int> nodes_;
unordered_map<int, unordered_set<int>> in_degree_;
unordered_map<int, unordered_set<int>> out_degree_;
};
};