{"id":546,"date":"2017-10-07T10:32:44","date_gmt":"2017-10-07T17:32:44","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=546"},"modified":"2018-04-19T08:30:22","modified_gmt":"2018-04-19T15:30:22","slug":"leetcode-685-redundant-connection-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-685-redundant-connection-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 685. Redundant Connection II"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 685. Redundant Connection II - \u5237\u9898\u627e\u5de5\u4f5c EP83\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/lnmJT5b4NlM?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>In this problem, a rooted tree is a\u00a0<b>directed<\/b>\u00a0graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.<\/p>\n<p>The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, &#8230;, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.<\/p>\n<p>The resulting graph is given as a 2D-array of\u00a0<code>edges<\/code>. Each element of\u00a0<code>edges<\/code>\u00a0is a pair\u00a0<code>[u, v]<\/code>\u00a0that represents a\u00a0<b>directed<\/b>\u00a0edge connecting nodes\u00a0<code>u<\/code>\u00a0and\u00a0<code>v<\/code>, where\u00a0<code>u<\/code>\u00a0is a parent of child\u00a0<code>v<\/code>.<\/p>\n<p>Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"\">Input: [[1,2], [1,3], [2,3]]\r\nOutput: [2,3]\r\nExplanation: The given directed graph will be like this:\r\n  1\r\n \/ \\\r\nv   v\r\n2--&gt;3\r\n<\/pre>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"\">Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]\r\nOutput: [4,1]\r\nExplanation: The given directed graph will be like this:\r\n5 &lt;- 1 -&gt; 2\r\n     ^    |\r\n     |    v\r\n     4 &lt;- 3\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>The size of the input 2D-array will be between 3 and 1000.<\/li>\n<li>Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.<\/li>\n<\/ul>\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>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p><strong>Idea: <\/strong><\/p>\n<p>Union Find<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/685-ep83.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-548\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/685-ep83.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/685-ep83.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/685-ep83-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/685-ep83-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/685-ep83-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><strong>Time complexity<\/strong>: O(nlog*n) ~ O(n)<\/p>\n<p><strong>Space complexity<\/strong>: O(n)<\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 6 ms\r\nclass Solution {\r\npublic:\r\n    vector&lt;int&gt; findRedundantDirectedConnection(vector&lt;vector&lt;int&gt;&gt;&amp; edges) {\r\n        \r\n        vector&lt;int&gt; parents(edges.size() + 1, 0);\r\n        vector&lt;int&gt; roots(edges.size() + 1, 0);       \r\n        vector&lt;int&gt; sizes(edges.size() + 1, 1);\r\n        \r\n        vector&lt;int&gt; ans1;\r\n        vector&lt;int&gt; ans2;\r\n        \r\n        for(auto&amp; edge: edges) {\r\n            int u = edge[0];\r\n            int v = edge[1];\r\n            \r\n            \/\/ A node has two parents\r\n            if (parents[v] &gt; 0) {\r\n                ans1 = {parents[v], v};\r\n                ans2 = edge;\r\n                \r\n                \/\/ Delete the later edge\r\n                edge[0] = edge[1] = -1;\r\n            }\r\n            \r\n            parents[v] = u;\r\n        }\r\n        \r\n        for(const auto&amp; edge: edges) {\r\n            int u = edge[0];\r\n            int v = edge[1];\r\n            \r\n            \/\/ Invalid edge (we deleted in step 1)\r\n            if (u &lt; 0 || v &lt; 0) continue;\r\n            \r\n            if (!roots[u]) roots[u] = u;\r\n            if (!roots[v]) roots[v] = v;\r\n            int pu = find(u, roots);\r\n            int pv = find(v, roots);\r\n            \r\n            \/\/ Both u and v are already in the tree\r\n            if (pu == pv)\r\n                return ans1.empty() ? edge : ans1;\r\n            \r\n            \/\/ Unoin, always merge smaller set (pv) to larger set (pu)\r\n            if (sizes[pv] &gt; sizes[pu])\r\n                swap(pu, pv);\r\n            \r\n            roots[pv] = pu;\r\n            sizes[pu] += sizes[pv];\r\n        }\r\n        \r\n        return ans2;\r\n    }\r\n    \r\nprivate:\r\n    int find(int node, vector&lt;int&gt;&amp; roots) {\r\n        while (roots[node] != node) {\r\n            roots[node] = roots[roots[node]];\r\n            node = roots[node];\r\n        }\r\n        return node;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>C++ \/ without using Union find<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 6 ms\r\nclass Solution {\r\npublic:\r\n    vector&lt;int&gt; findRedundantDirectedConnection(vector&lt;vector&lt;int&gt;&gt;&amp; edges) {\r\n        \r\n        vector&lt;int&gt; parents(edges.size() + 1, 0);        \r\n        \r\n        vector&lt;int&gt; ans1;\r\n        vector&lt;int&gt; ans2;        \r\n        \r\n        bool dup_parents = false;\r\n        \r\n        for(auto&amp; edge: edges) {\r\n            int u = edge[0];\r\n            int v = edge[1];\r\n            \r\n            \/\/ A node has two parents\r\n            if (parents[v] &gt; 0) {\r\n                ans1 = {parents[v], v};\r\n                ans2 = edge;\r\n                dup_parents = true;\r\n                \/\/ Delete the later edge\r\n                edge[0] = edge[1] = -1;\r\n            } else {            \r\n                parents[v] = u;\r\n            }\r\n        }\r\n        \r\n        \/\/ Reset parents\r\n        parents = vector&lt;int&gt;(edges.size() + 1, 0);\r\n        \r\n        for(const auto&amp; edge: edges) {\r\n            int u = edge[0];\r\n            int v = edge[1];\r\n            \r\n            \/\/ Invalid edge (we deleted in step 1)\r\n            if (u &lt; 0 || v &lt; 0) continue;\r\n            \r\n            parents[v] = u;\r\n            \r\n            if (cycle(v, parents))\r\n                return dup_parents ? ans1 : edge;\r\n        }\r\n        \r\n        return ans2;\r\n    }    \r\nprivate:\r\n    bool cycle(int v, const vector&lt;int&gt;&amp; parents) {\r\n        int u = parents[v];        \r\n        while (u) {\r\n            if (u == v) return true;            \r\n            u = parents[u];\r\n        }\r\n        return false;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>Python<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRuntime: 62 ms\r\n\"\"\"\r\nclass Solution:\r\n    def findRedundantDirectedConnection(self, edges):\r\n        def cycle(v, p):\r\n            u = p[v]\r\n            while u != 0:\r\n                if u == v: return True\r\n                u = p[u]\r\n            return False\r\n        \r\n        n = len(edges)\r\n        p = [0] * (n + 1)\r\n        \r\n        ans1 = []\r\n        ans2 = []\r\n        dup_p = False\r\n        \r\n        for e in edges:\r\n            u, v = e\r\n            if p[v] &gt; 0:\r\n                ans1 = [p[v], v]\r\n                ans2 = [u, v]\r\n                dup_p = True\r\n                e[0] = e[1] = -1\r\n            else:\r\n                p[v] = u\r\n        \r\n        p = [0] * (n + 1)\r\n        \r\n        for u, v in edges:\r\n            if u &lt; 0: continue\r\n            p[v] = u\r\n            if cycle(v, p):\r\n                return ans1 if dup_p else [u, v]\r\n        \r\n        return ans2\r\n<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: In this problem, a rooted tree is a\u00a0directed\u00a0graph such that, there is exactly one node (the root) for which all other nodes are descendants&#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":[123,124,113],"class_list":["post-546","post","type-post","status-publish","format-standard","hentry","category-graph","tag-cycle","tag-directed-graph","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/546","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=546"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/546\/revisions"}],"predecessor-version":[{"id":2567,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/546\/revisions\/2567"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=546"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=546"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=546"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}