{"id":7954,"date":"2021-01-09T22:12:41","date_gmt":"2021-01-10T06:12:41","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7954"},"modified":"2021-01-09T22:23:10","modified_gmt":"2021-01-10T06:23:10","slug":"leetcode-1719-number-of-ways-to-reconstruct-a-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1719-number-of-ways-to-reconstruct-a-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1719. Number Of Ways To Reconstruct A Tree"},"content":{"rendered":"\n<p>You are given an array&nbsp;<code>pairs<\/code>, where&nbsp;<code>pairs[i] = [x<sub>i<\/sub>, y<sub>i<\/sub>]<\/code>, and:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>There are no duplicates.<\/li><li><code>x<sub>i<\/sub>&nbsp;&lt; y<sub>i<\/sub><\/code><\/li><\/ul>\n\n\n\n<p>Let&nbsp;<code>ways<\/code>&nbsp;be the number of rooted trees that satisfy the following conditions:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The tree consists of nodes whose values appeared in&nbsp;<code>pairs<\/code>.<\/li><li>A pair&nbsp;<code>[x<sub>i<\/sub>, y<sub>i<\/sub>]<\/code>&nbsp;exists in&nbsp;<code>pairs<\/code>&nbsp;<strong>if and only if<\/strong>&nbsp;<code>x<sub>i<\/sub><\/code>&nbsp;is an ancestor of&nbsp;<code>y<sub>i<\/sub><\/code>&nbsp;or&nbsp;<code>y<sub>i<\/sub><\/code>&nbsp;is an ancestor of&nbsp;<code>x<sub>i<\/sub><\/code>.<\/li><li><strong>Note:<\/strong>&nbsp;the tree does not have to be a binary tree.<\/li><\/ul>\n\n\n\n<p>Two ways are considered to be different if there is at least one node that has different parents in both ways.<\/p>\n\n\n\n<p>Return:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>0<\/code>&nbsp;if&nbsp;<code>ways == 0<\/code><\/li><li><code>1<\/code>&nbsp;if&nbsp;<code>ways == 1<\/code><\/li><li><code>2<\/code>&nbsp;if&nbsp;<code>ways &gt; 1<\/code><\/li><\/ul>\n\n\n\n<p>A&nbsp;<strong>rooted tree<\/strong>&nbsp;is a tree that has a single root node, and all edges are oriented to be outgoing from the root.<\/p>\n\n\n\n<p>An&nbsp;<strong>ancestor<\/strong>&nbsp;of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/12\/03\/trees2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> pairs = [[1,2],[2,3]]\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> There is exactly one valid rooted tree, which is shown in the above figure.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/12\/03\/tree.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> pairs = [[1,2],[2,3],[1,3]]\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> There are multiple valid rooted trees. Three of them are shown in the above figures.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> pairs = [[1,2],[2,3],[2,4],[1,5]]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> There are no valid rooted trees.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= pairs.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= x<sub>i&nbsp;<\/sub>&lt; y<sub>i<\/sub>&nbsp;&lt;= 500<\/code><\/li><li>The elements in&nbsp;<code>pairs<\/code>&nbsp;are unique.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Bitset<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(E*V)<br>Space complexity: O(V^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int checkWays(vector<vector<int>>& pairs) {\n    \/\/ Construct a map, key is the node, value is the accessible nodes.\n    unordered_map<int, bitset<501>> m;\n    for (auto& e : pairs) \n      m[e[0]][e[0]] = m[e[1]][e[1]] = m[e[0]][e[1]] = m[e[1]][e[0]] = 1;\n    \n    \/\/ The tree must have one+ node\/root that has paths to all the nodes.\n    if (!any_of(begin(m), end(m), [&m](const auto& kv) {\n      return kv.second.count() == m.size();})) return 0;\n    \n    int multiple = 0;\n    for (const auto& e : pairs) {\n      \/\/ For each pair, check whether one can be the parent of another\n      \/\/ that can conver all the children nodes.\n      const auto& all = m[e[0]] | m[e[1]];\n      const int r0 = m[e[0]] == all;\n      const int r1 = m[e[1]] == all;\n      if (r0 + r1 == 0) return 0;\n      \/\/ If both can be parents, there can be multiple trees.\n      multiple |= r0 * r1;\n    }\n    return 1 + multiple;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n# Author: Huahua\nclass Solution:\n  def checkWays(self, pairs: List[List[int]]) -> int:\n    m = defaultdict(set)\n    for u, v in pairs:\n      m[u] |= set((u, v))\n      m[v] |= set((u, v))\n    \n    if not any(len(m[x]) == len(m) for x in m):\n      return 0\n    \n    multiple = 0\n    for u, v in pairs:\n      union = m[u] | m[v]\n      ru, rv = int(m[u] == union), int(m[v] == union)\n      if not ru + rv: return 0\n      multiple |= ru * rv\n    return 1 + multiple\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an array&nbsp;pairs, where&nbsp;pairs[i] = [xi, yi], and: There are no duplicates. xi&nbsp;&lt; yi Let&nbsp;ways&nbsp;be the number of rooted trees that satisfy the&#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":[232,77,217,28],"class_list":["post-7954","post","type-post","status-publish","format-standard","hentry","category-graph","tag-bitset","tag-graph","tag-hard","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7954","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=7954"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7954\/revisions"}],"predecessor-version":[{"id":7958,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7954\/revisions\/7958"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7954"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7954"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7954"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}