LeetCode 210. Course Schedule II
原题链接
中等
作者:
JasonSun
,
2020-08-29 09:43:00
,
所有人可见
,
阅读 351
Topoligical Sort (DFS)
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
enum state_t {untouched, explore, done};
const auto G = [&](std::vector<std::vector<int>> self = {}) {
self.resize(numCourses);
for (const auto & e: prerequisites) {
const auto [u, v] = std::pair{e[0], e[1]};
self[v].emplace_back(u);
}
return self;
}();
const auto solution = [&](std::optional<std::vector<int>> self = std::make_optional(std::vector<int>{})) {
auto state = std::vector<state_t>(numCourses, untouched);
std::function<void(int)> fold = [&](int u) {
if (state[u] == explore) {
self.reset();
return;
}
else {
std::exchange(state[u], explore);
for (const auto v : G[u]) {
if (state[v] != done) {
fold(v);
}
}
std::exchange(state[u], done);
if (self.has_value()) {
self.value().emplace_back(u);
}
}
};
for (int u = 0; u < numCourses and self.has_value(); ++u) {
if (state[u] == untouched) {
fold(u);
}
}
if (self.has_value()) {
return std::reverse(std::begin(self.value()), std::end(self.value())), self.value();
}
else {
return std::vector<int>{};
}
}();
return solution;
}
};
Topological Sort (BFS)
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
const auto G = [&](std::vector<std::vector<int>> self = {}) {
self.resize(numCourses);
for (const auto& e : prerequisites) {
const auto [u, v] = std::pair{e[0], e[1]};
self[v].emplace_back(u);
}
return self;
}();
const auto indegree = [&](std::vector<int> self = {}) {
self.resize(numCourses, 0);
for (int u = 0; u < numCourses; ++u) {
for (const auto v : G[u]) {
++self[v];
}
}
return self;
}();
const auto solution = [&](std::vector<int> self = {}) {
// mutable states
auto Q = [&](std::deque<int> self = {}) {
for (int u = 0; u < numCourses; ++u) {
if (indegree[u] == 0) {
self.emplace_back(u);
}
}
return self;
}();
std::function<void(void)> bfs = [&, indegree = indegree]() mutable {
if (std::empty(Q)) {
if ((int)std::size(self) != numCourses) {
self.clear();
}
return;
}
else {
const auto u = Q.front();
Q.pop_front();
self.emplace_back(u);
for (const auto v : G[u]) {
if (--indegree[v] == 0) {
Q.emplace_back(v);
}
}
bfs();
}
};
return bfs(), self;
}();
return solution;
}
};