diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/course_schedule.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/course_schedule.cpp')
-rw-r--r-- | other/course_schedule.cpp | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/other/course_schedule.cpp b/other/course_schedule.cpp new file mode 100644 index 0000000..4a249d2 --- /dev/null +++ b/other/course_schedule.cpp @@ -0,0 +1,44 @@ +// 207. Course Schedule +#include "leetcode.h" + +/* + * there are a total of 'num_courses' courses you have to take labeled from 0 to + * 'num_courses - 1'. you are given an array 'prerequisites' where + * 'prerequisites[i] = [ai, bi]' indicates that you must take course 'bi' first + * if you want to take course 'ai'. return true if you can finish all courses, + * otherwise, return false + */ + +class Solution { + bool is_cycle(vector<int> adj[], vector<int> &vis, int id) { + if (vis[id] == 1) + return true; + if (!vis[id]) { + vis[id] = 1; + for (auto edge : adj[id]) + if (is_cycle(adj, vis, edge)) + return true; + } + vis[id] = 2; + return false; + } + +public: + bool canFinish(int num_courses, vvd & prerequisites) { + vector<int> adj[num_courses]; + for (auto edge : prerequisites) + adj[edge[1]].push_back(edge[0]); + vector<int> vis(num_courses, 0); + for (int i = 0; i < num_courses; i++) + if (is_cycle(adj, vis, i)) + return false; + return true; + } +}; + +int main() { + Solution obj; + vvd p1 = {{1, 0}}, p2 = {{1, 0}, {0, 1}}; + printf("%d\n", obj.canFinish(2, p1)); // expect: 1 + printf("%d\n", obj.canFinish(2, p2)); // expect: 0 +} |