{"id":654,"date":"2017-10-20T23:26:36","date_gmt":"2017-10-21T06:26:36","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=654"},"modified":"2019-09-29T21:42:57","modified_gmt":"2019-09-30T04:42:57","slug":"leetcode-207-course-schedule","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-207-course-schedule\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 207. Course Schedule"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 207. Course Schedule - \u5237\u9898\u627e\u5de5\u4f5c EP93\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/M6SBePBMznU?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>There are a total of&nbsp;<i>n<\/i>&nbsp;courses you have to take, labeled from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n - 1<\/code>.<\/p>\n<p>Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:&nbsp;<code>[0,1]<\/code><\/p>\n<p>Given the total number of courses and a list of prerequisite&nbsp;<b>pairs<\/b>, is it possible for you to finish all courses?<\/p>\n<p>For example:<\/p>\n<pre>2, [[1,0]]<\/pre>\n<p>There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.<\/p>\n<pre>2, [[1,0],[0,1]]<\/pre>\n<p>There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.<\/p>\n<p><script async=\"\" src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script><br \/>\n     (adsbygoogle = window.adsbygoogle || []).push({});<br \/>\n<\/script><\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>Finding cycles O(n^2) -&gt; Topological sort O(n)<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-659\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-658\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/207-ep93-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<h1><strong>Solution 1: Topological Sort<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\n\/\/ Time complexity: O(n)\n\/\/ Runtime: 12 ms\nclass Solution {\npublic:\n    bool canFinish(int numCourses, vector&lt;pair&lt;int, int&gt;&gt;&amp; prerequisites) {\n        \n        graph_ = vector&lt;vector&lt;int&gt;&gt;(numCourses);\n        \n        for(const auto&amp; p : prerequisites)\n            graph_[p.first].push_back(p.second);\n        \n        \/\/ states: 0 = unkonwn, 1 == visiting, 2 = visited\n        vector&lt;int&gt; v(numCourses, 0);\n        \n        for(int i = 0; i &lt; numCourses; ++i)\n            if(dfs(i, v)) return false;\n        \n        return true;\n    }\n    \nprivate:\n    vector&lt;vector&lt;int&gt;&gt; graph_;\n    bool dfs(int cur, vector&lt;int&gt;&amp; v) {\n        if(v[cur] == 1) return true;\n        if(v[cur] == 2) return false;\n        \n        v[cur] = 1;\n        \n        for(const int t : graph_[cur])\n            if(dfs(t, v)) return true;\n        \n        v[cur] = 2;\n        \n        return false;\n    }\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\n\/\/ Runtime: 6 ms\n\/\/ HashMap is slower than ArrayList in this problem.\nclass Solution {    \n    public boolean canFinish(int numCourses, int[][] prerequisites) {        \n        ArrayList&lt;ArrayList&lt;Integer&gt;&gt; graph = new ArrayList&lt;&gt;();\n        \n        for (int i = 0; i &lt; numCourses; ++i)\n            graph.add(new ArrayList&lt;Integer&gt;());\n        \n        for (int i = 0; i &lt; prerequisites.length; ++i) {\n            int course = prerequisites[i][0];\n            int prerequisite = prerequisites[i][1];            \n            graph.get(course).add(prerequisite);\n        }\n        \n        int[] visited = new int[numCourses];\n        for (int i = 0; i &lt; numCourses; ++i)\n            if (dfs(i, graph, visited)) return false;\n        \n        return true;\n    }\n    \n    private boolean dfs(int curr, ArrayList&lt;ArrayList&lt;Integer&gt;&gt; graph, int[] visited) {\n        if (visited[curr] == 1) return true;\n        if (visited[curr] == 2) return false;\n        \n        visited[curr] = 1;\n                \n        for (int next : graph.get(curr))\n            if (dfs(next, graph, visited)) return true;\n        \n        visited[curr] = 2;\n        return false;\n    }\n\n}<\/pre>\n<\/div><\/div>\n<p><script async=\"\" src=\"https:\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display:block\" data-ad-format=\"fluid\" data-ad-layout-key=\"-fb+5w+4e-db+86\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"2162692788\"><\/ins><br \/>\n<script><br \/>\n     (adsbygoogle = window.adsbygoogle || []).push({});<br \/>\n<\/script><\/p>\n<h1><strong>Solution 2: DFS&nbsp;Finding cycles<\/strong><\/h1>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\n\/\/ Time complexity: O(n^2)\n\/\/ Runtime: 179 ms\nclass Solution {\npublic:\n    bool canFinish(int numCourses, vector&lt;pair&lt;int, int&gt;&gt;&amp; prerequisites) {\n        \n        graph_.clear();\n        \n        for(const auto&amp; p : prerequisites)\n            graph_[p.first].insert(p.second);\n        \n        for (int i = 0; i &lt; numCourses; ++i) {\n            vector&lt;int&gt; visited(numCourses, 0);\n            if (cycle(i, i, visited)) return false;\n        }\n        \n        return true;\n    }\n    \nprivate:\n    unordered_map&lt;int, unordered_set&lt;int&gt;&gt; graph_;\n    \n    bool cycle(int start, int curr, vector&lt;int&gt;&amp; visited) {        \n        if (curr == start &amp;&amp; visited[start]) return true;\n        if (!graph_.count(curr)) return false;\n        \n        for (const int next : graph_.at(curr)) {\n            if (visited[next]) continue;\n            visited[next] = true;\n            if (cycle(start, next, visited)) return true;\n        }\n        return false;\n    }\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Related Pr0blems:<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-210-course-schedule-ii\/\">\u82b1\u82b1\u9171 LeetCode 210. Course Schedule II<\/a><\/li>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-802-find-eventual-safe-states\/\">\u82b1\u82b1\u9171 LeetCode 802. Find Eventual Safe States<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem: There are a total of&nbsp;n&nbsp;courses you have to take, labeled from&nbsp;0&nbsp;to&nbsp;n &#8211; 1. Some courses may have prerequisites, for example to take course 0&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76,164],"tags":[123,124,77,177,137],"class_list":["post-654","post","type-post","status-publish","format-standard","hentry","category-graph","category-medium","tag-cycle","tag-directed-graph","tag-graph","tag-medium","tag-topological-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/654","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=654"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/654\/revisions"}],"predecessor-version":[{"id":5640,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/654\/revisions\/5640"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=654"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=654"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=654"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}