Skip to content

Commit 74ce81a

Browse files
liuyuboboboliuyubobobo
committed
0210 solved.
1 parent fb44631 commit 74ce81a

File tree

5 files changed

+256
-1
lines changed

5 files changed

+256
-1
lines changed

‎0210-Course-Schedule-II/cpp-0210/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.13)
2+
project(cpp_0210)
3+
4+
set(CMAKE_CXX_STANDARD 11)
5+
6+
add_executable(cpp_0210 main3.cpp)

‎0210-Course-Schedule-II/cpp-0210/main.cpp

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
/// Source : https://leetcode.com/problems/course-schedule-ii/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-12-16
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <queue>
8+
9+
using namespace std;
10+
11+
12+
/// Using Priority Queue
13+
/// Time Complexity: O(ElogE)
14+
/// Space Complexity: O(V + E)
15+
class Solution {
16+
public:
17+
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
18+
19+
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
20+
vector<int> pre(numCourses, 0);
21+
vector<vector<int>> g(numCourses);
22+
for(const pair<int, int>& p: prerequisites){
23+
int from = p.second;
24+
int to = p.first;
25+
g[from].push_back(to);
26+
pre[to] ++;
27+
}
28+
29+
for(int i = 0; i < numCourses; i ++)
30+
pq.push(make_pair(pre[i], i));
31+
32+
vector<bool> learnt(numCourses, false);
33+
vector<int> res;
34+
while(!pq.empty()){
35+
int x = pq.top().first;
36+
int id = pq.top().second;
37+
pq.pop();
38+
39+
if(!learnt[id]){
40+
if(x) return {};
41+
42+
res.push_back(id);
43+
learnt[id] = true;
44+
45+
for(int next: g[id]){
46+
pre[next] --;
47+
pq.push(make_pair(pre[next], next));
48+
}
49+
}
50+
}
51+
52+
return res;
53+
}
54+
};
55+
56+
57+
void print_vec(const vector<int>& vec){
58+
for(int e: vec)
59+
cout << e << " ";
60+
cout << endl;
61+
}
62+
63+
int main() {
64+
65+
vector<pair<int, int>> pre1 = {{1,0}};
66+
print_vec(Solution().findOrder(2, pre1));
67+
// 0 1
68+
69+
vector<pair<int, int>> pre2 = {{1,0},{2,0},{3,1},{3,2}};
70+
print_vec(Solution().findOrder(4, pre2));
71+
// 0 1 2 3
72+
73+
return 0;
74+
}

‎0210-Course-Schedule-II/cpp-0210/main2.cpp

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
/// Source : https://leetcode.com/problems/course-schedule-ii/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-12-16
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <queue>
8+
9+
using namespace std;
10+
11+
12+
/// Using Queue is enough
13+
/// Since we are only interested in 0-indegree vertex :-)
14+
///
15+
/// Time Complexity: O(E)
16+
/// Space Complexity: O(V + E)
17+
class Solution {
18+
public:
19+
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
20+
21+
vector<int> pre(numCourses, 0);
22+
vector<vector<int>> g(numCourses);
23+
for(const pair<int, int>& p: prerequisites){
24+
int from = p.second;
25+
int to = p.first;
26+
g[from].push_back(to);
27+
pre[to] ++;
28+
}
29+
30+
queue<int> q;
31+
for(int i = 0; i < numCourses; i ++)
32+
if(pre[i] == 0)
33+
q.push(i);
34+
35+
vector<int> res;
36+
while(!q.empty()){
37+
int id = q.front();
38+
q.pop();
39+
40+
res.push_back(id);
41+
for(int next: g[id]){
42+
pre[next] --;
43+
if(pre[next] == 0)
44+
q.push(next);
45+
}
46+
}
47+
48+
if(res.size() == numCourses)
49+
return res;
50+
return {};
51+
}
52+
};
53+
54+
55+
void print_vec(const vector<int>& vec){
56+
for(int e: vec)
57+
cout << e << " ";
58+
cout << endl;
59+
}
60+
61+
int main() {
62+
63+
vector<pair<int, int>> pre1 = {{1,0}};
64+
print_vec(Solution().findOrder(2, pre1));
65+
// 0 1
66+
67+
vector<pair<int, int>> pre2 = {{1,0},{2,0},{3,1},{3,2}};
68+
print_vec(Solution().findOrder(4, pre2));
69+
// 0 1 2 3
70+
71+
return 0;
72+
}

‎0210-Course-Schedule-II/cpp-0210/main3.cpp

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
/// Source : https://leetcode.com/problems/course-schedule-ii/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-12-16
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <stack>
8+
9+
using namespace std;
10+
11+
12+
/// Topological Order based on DFS
13+
/// Time Complexity: O(V + E)
14+
/// Space Complexity: O(V + E)
15+
class Solution {
16+
public:
17+
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
18+
19+
vector<vector<int>> g(numCourses);
20+
for(const pair<int, int>& p: prerequisites){
21+
int from = p.second;
22+
int to = p.first;
23+
g[from].push_back(to);
24+
}
25+
26+
if(hasCircle(g)) return {};
27+
return topoOrder(g);
28+
}
29+
30+
private:
31+
bool hasCircle(const vector<vector<int>>& g){
32+
33+
vector<bool> visited(g.size(), false);
34+
vector<bool> onPath(g.size(), false);
35+
for(int i = 0; i < g.size(); i ++)
36+
if(!visited[i])
37+
if(circleDFS(g, i, visited, onPath))
38+
return true;
39+
return false;
40+
}
41+
42+
bool circleDFS(const vector<vector<int>>& g, int v,
43+
vector<bool>& visited, vector<bool>& onPath){
44+
45+
visited[v] = true;
46+
onPath[v] = true;
47+
for(int next: g[v])
48+
if(!visited[next]){
49+
if(circleDFS(g, next, visited, onPath))
50+
return true;
51+
}
52+
else if(onPath[next])
53+
return true;
54+
55+
onPath[v] = false;
56+
return false;
57+
}
58+
59+
vector<int> topoOrder(const vector<vector<int>>& g){
60+
61+
vector<bool> visited(g.size(), false);
62+
stack<int> st;
63+
for(int i = 0; i < g.size(); i ++)
64+
if(!visited[i])
65+
topoDFS(g, i, visited, st);
66+
67+
vector<int> res;
68+
while(!st.empty()){
69+
res.push_back(st.top());
70+
st.pop();
71+
}
72+
return res;
73+
}
74+
75+
void topoDFS(const vector<vector<int>>& g, int v, vector<bool>& visited, stack<int>& st){
76+
77+
visited[v] = true;
78+
for(int next: g[v])
79+
if(!visited[next])
80+
topoDFS(g, next, visited, st);
81+
st.push(v);
82+
}
83+
};
84+
85+
86+
void print_vec(const vector<int>& vec){
87+
for(int e: vec)
88+
cout << e << " ";
89+
cout << endl;
90+
}
91+
92+
int main() {
93+
94+
vector<pair<int, int>> pre1 = {{1,0}};
95+
print_vec(Solution().findOrder(2, pre1));
96+
// 0 1
97+
98+
vector<pair<int, int>> pre2 = {{1,0},{2,0},{3,1},{3,2}};
99+
print_vec(Solution().findOrder(4, pre2));
100+
// 0 1 2 3
101+
102+
return 0;
103+
}

‎readme.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -214,7 +214,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
214214
| | | | | | |
215215
| 208 | [Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/description/) | [solution](https://leetcode.com/problems/implement-trie-prefix-tree/solution/) | [C++](0208-Implement-Trie-Prefix-Tree/cpp-0208/) | | |
216216
| 209 | [Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/description/) | [solution](https://leetcode.com/problems/minimum-size-subarray-sum/solution/) | [C++](0209-Minimum-Size-Subarray-Sum/cpp-0209/) | [Java](0209-Minimum-Size-Subarray-Sum/java-0209/src/) | |
217-
| | | | | | |
217+
| 210 | [Course Schedule II](https://leetcode.com/problems/course-schedule-ii/) | [solution](https://leetcode.com/problems/course-schedule-ii/solution/) | [C++](0210-Course-Schedule-II/cpp-0210/) | | |
218218
| 211 | [Add and Search Word - Data structure design](https://leetcode.com/problems/add-and-search-word-data-structure-design/description/) | [无] | [C++](0211-Add-and-Search-Word-Data-structure-design/cpp-0211/) | | |
219219
| | | | | | |
220220
| 213 | [House Robber II](https://leetcode.com/problems/house-robber-ii/description/) | [无] | [C++](0213/House-Robber-II/cpp-0213/) | | |

0 commit comments

Comments
 (0)