{"id":1228,"date":"2017-12-13T22:35:21","date_gmt":"2017-12-14T06:35:21","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1228"},"modified":"2018-09-04T08:25:36","modified_gmt":"2018-09-04T15:25:36","slug":"leetcode-210-course-schedule-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-210-course-schedule-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 210. Course Schedule II"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 210. Course Schedule II - \u5237\u9898\u627e\u5de5\u4f5c EP133\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/Qqgck2ijUjU?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<h1><strong>Problem<\/strong><\/h1>\n<p>There are a total of\u00a0<i>n<\/i>\u00a0courses you have to take, labeled from\u00a0<code>0<\/code>\u00a0to\u00a0<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:\u00a0<code>[0,1]<\/code><\/p>\n<p>Given the total number of courses and a list of prerequisite\u00a0<b>pairs<\/b>, return the ordering of courses you should take to finish all courses.<\/p>\n<p>There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.<\/p>\n<p>For example:<\/p>\n<pre class=\"theme:classic toolbar:2 lang:default decode:true\">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 the correct course order is\u00a0<code>[0,1]<\/code><\/p>\n<pre class=\"theme:classic toolbar:2 lang:default decode:true \">4, [[1,0],[2,0],[3,1],[3,2]]<\/pre>\n<p>There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is\u00a0<code>[0,1,2,3]<\/code>. Another correct ordering is<code>[0,2,1,3]<\/code>.<\/p>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>The input prerequisites is a graph represented by\u00a0<b>a list of edges<\/b>, not adjacency matrices. Read more about\u00a0<a href=\"https:\/\/www.khanacademy.org\/computing\/computer-science\/algorithms\/graph-representation\/a\/representing-graphs\" target=\"_blank\" rel=\"noopener\">how a graph is represented<\/a>.<\/li>\n<li>You may assume that there are no duplicate edges in the input prerequisites.<\/li>\n<\/ol>\n<p><strong>\u9898\u76ee\u5927\u610f\uff1a<\/strong><\/p>\n<p>\u7ed9\u4f60\u4e00\u4e9b\u8bfe\u7a0b\u548c\u5b83\u7684\u5148\u4fee\u8bfe\u7a0b\uff0c\u8ba9\u4f60\u8f93\u51fa\u4fee\u8bfe\u987a\u5e8f\u3002\u5982\u679c\u65e0\u6cd5\u4fee\u5b8c\u6240\u6709\u8bfe\u7a0b\uff0c\u8fd4\u56de\u7a7a\u6570\u7ec4\u3002<\/p>\n<p><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>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1252\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/210-ep133.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/210-ep133.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/210-ep133-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/210-ep133-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Idea<\/strong><\/h1>\n<p>Topological sorting<\/p>\n<p>\u62d3\u6251\u6392\u5e8f<\/p>\n<h1><strong>Solution 1:\u00a0Topological Sorting<\/strong><\/h1>\n<p>Time complexity: O(V+E)<\/p>\n<p>Space complexity: O(V+E)<\/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\r\n\/\/ Runtime: 16 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; findOrder(int numCourses, vector&lt;pair&lt;int, int&gt;&gt;&amp; prerequisites) {\r\n    vector&lt;vector&lt;int&gt;&gt; graph(numCourses);    \r\n    for(const auto&amp; p : prerequisites)\r\n      graph[p.second].push_back(p.first);\r\n\r\n    \/\/ states: 0 = unkonwn, 1 == visiting, 2 = visited\r\n    vector&lt;int&gt; v(numCourses, 0);\r\n    vector&lt;int&gt; ans;\r\n    \r\n    for (int i = 0; i &lt; numCourses; ++i)\r\n      if (dfs(i, graph, v, ans)) return {};\r\n\r\n    std::reverse(ans.begin(), ans.end());\r\n    return ans;\r\n  }\r\nprivate:\r\n  bool dfs(int cur, vector&lt;vector&lt;int&gt;&gt;&amp; graph, vector&lt;int&gt;&amp; v, vector&lt;int&gt;&amp; ans) {\r\n    if (v[cur] == 1) return true;\r\n    if (v[cur] == 2) return false;\r\n\r\n    v[cur] = 1;\r\n    \r\n    for (const int t : graph[cur])\r\n      if (dfs(t, graph, v, ans)) return true;\r\n    \r\n    v[cur] = 2;\r\n    ans.push_back(cur);\r\n\r\n    return false;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 83 ms\r\nclass Solution {\r\n    public int[] findOrder(int numCourses, int[][] prerequisites) {\r\n        ArrayList&lt;ArrayList&lt;Integer&gt;&gt; graph = new ArrayList&lt;&gt;();\r\n        \r\n        for (int i = 0; i &lt; numCourses; ++i)\r\n            graph.add(new ArrayList&lt;Integer&gt;());\r\n        \r\n        for (int i = 0; i &lt; prerequisites.length; ++i) {\r\n            int course = prerequisites[i][0];\r\n            int prerequisite = prerequisites[i][1];            \r\n            graph.get(course).add(prerequisite);\r\n        }\r\n        \r\n        int[] visited = new int[numCourses];\r\n        List&lt;Integer&gt; ans = new ArrayList&lt;Integer&gt;();\r\n        Integer index = numCourses;\r\n        for (int i = 0; i &lt; numCourses; ++i)\r\n            if (dfs(i, graph, visited, ans)) return new int[0];        \r\n        \r\n        return ans.stream().mapToInt(i-&gt;i).toArray();\r\n    }\r\n    \r\n    private boolean dfs(int curr, ArrayList&lt;ArrayList&lt;Integer&gt;&gt; graph, int[] visited, List&lt;Integer&gt; ans) {\r\n        if (visited[curr] == 1) return true;\r\n        if (visited[curr] == 2) return false;\r\n        \r\n        visited[curr] = 1;\r\n        for (int next : graph.get(curr))\r\n            if (dfs(next, graph, visited, ans)) return true;\r\n        \r\n        visited[curr] = 2;\r\n        ans.add(curr);\r\n        \r\n        return false;\r\n    }    \r\n}<\/pre>\n<\/div><\/div>\n<h1><strong>Related Problems:<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-207-course-schedule\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 207. Course Schedule<\/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\u00a0n\u00a0courses you have to take, labeled from\u00a00\u00a0to\u00a0n &#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,137],"class_list":["post-1228","post","type-post","status-publish","format-standard","hentry","category-graph","category-medium","tag-cycle","tag-directed-graph","tag-graph","tag-topological-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1228","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=1228"}],"version-history":[{"count":13,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1228\/revisions"}],"predecessor-version":[{"id":3864,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1228\/revisions\/3864"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1228"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}