{"id":2847,"date":"2018-05-27T09:25:19","date_gmt":"2018-05-27T16:25:19","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2847"},"modified":"2018-05-28T11:48:57","modified_gmt":"2018-05-28T18:48:57","slug":"leetcode-841-keys-and-rooms","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-841-keys-and-rooms\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 841. Keys and Rooms"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 841. Keys and Rooms - \u5237\u9898\u627e\u5de5\u4f5c EP190\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/y46WQ5KMiD8?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>Problem<\/h1>\n<p>There are\u00a0<code>N<\/code>\u00a0rooms and you start in room\u00a0<code>0<\/code>.\u00a0 Each room has a distinct number in\u00a0<code>0, 1, 2, ..., N-1<\/code>, and each room may have\u00a0some keys to access the next room.<\/p>\n<p>Formally, each room\u00a0<code>i<\/code>\u00a0has a list of keys\u00a0<code>rooms[i]<\/code>, and each key\u00a0<code>rooms[i][j]<\/code>\u00a0is an integer in\u00a0<code>[0, 1, ..., N-1]<\/code>\u00a0where\u00a0<code>N = rooms.length<\/code>.\u00a0 A key\u00a0<code>rooms[i][j] = v<\/code>\u00a0opens the room with number\u00a0<code>v<\/code>.<\/p>\n<p>Initially, all the rooms start locked (except for room\u00a0<code>0<\/code>).<\/p>\n<p>You can walk back and forth between rooms freely.<\/p>\n<p>Return\u00a0<code>true<\/code>\u00a0if and only if you can enter\u00a0every room.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>[[1],[2],[3],[]]\r\n<strong>Output: <\/strong>true\r\n<strong>Explanation:  <\/strong>\r\nWe start in room 0, and pick up key 1.\r\nWe then go to room 1, and pick up key 2.\r\nWe then go to room 2, and pick up key 3.\r\nWe then go to room 3.  Since we were able to go to every room, we return true.\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>[[1,3],[3,0,1],[2],[0]]\r\n<strong>Output: <\/strong>false\r\n<strong>Explanation: <\/strong>We can't enter the room with number 2.\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li><code>1 &lt;= rooms.length &lt;=\u00a01000<\/code><\/li>\n<li><code>0 &lt;= rooms[i].length &lt;= 1000<\/code><\/li>\n<li>The number of keys in all rooms combined is at most\u00a0<code>3000<\/code>.<\/li>\n<\/ol>\n<h1><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2858\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/05\/841-ep190.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/05\/841-ep190.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/05\/841-ep190-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/05\/841-ep190-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/h1>\n<h1><strong>Solution: DFS<\/strong><\/h1>\n<p>Time complexity: O(V + E)<\/p>\n<p>Space complexity: O(V)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 12 ms\r\nclass Solution {\r\npublic:\r\n  bool canVisitAllRooms(vector&lt;vector&lt;int&gt;&gt;&amp; rooms) {\r\n    unordered_set&lt;int&gt; visited;\r\n    dfs(rooms, 0, visited);\r\n    return visited.size() == rooms.size();\r\n  }\r\nprivate:\r\n  void dfs(const vector&lt;vector&lt;int&gt;&gt;&amp; rooms, \r\n           int cur, unordered_set&lt;int&gt;&amp; visited) {\r\n    if (visited.count(cur)) return;\r\n    visited.insert(cur);\r\n    for (int nxt : rooms[cur])\r\n      dfs(rooms, nxt, visited);\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem There are\u00a0N\u00a0rooms and you start in room\u00a00.\u00a0 Each room has a distinct number in\u00a00, 1, 2, &#8230;, N-1, and each room may have\u00a0some keys&#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],"tags":[102,33],"class_list":["post-2847","post","type-post","status-publish","format-standard","hentry","category-graph","tag-connected-components","tag-dfs","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2847","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=2847"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2847\/revisions"}],"predecessor-version":[{"id":2859,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2847\/revisions\/2859"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2847"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2847"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2847"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}