# 1719. Number Of Ways To Reconstruct A Tree

• Time: $O(n)$
• Space: $O(500 + n) = O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 class Solution { public: int checkWays(vector>& pairs) { constexpr int kMax = 501; unordered_map> graph; vector degrees(kMax); vector> connected(kMax, vector(kMax)); for (const vector& pair : pairs) { const int u = pair[0]; const int v = pair[1]; graph[u].push_back(v); graph[v].push_back(u); ++degrees[u]; ++degrees[v]; connected[u][v] = true; connected[v][u] = true; } // For each node, sort its children by degrees descendingly. for (auto& [_, children] : graph) sort(children.begin(), children.end(), [°rees](int a, int b) { return degrees[b] < degrees[a]; }); const int root = getRoot(degrees, graph.size()); if (root == -1) return 0; if (!dfs(graph, root, degrees, connected, {}, vector(kMax))) return 0; return hasMoreThanOneWay ? 2 : 1; } private: bool hasMoreThanOneWay = false; // Returns the root by finding the node with a degrees equal to n - 1. int getRoot(const vector& degrees, int n) { for (int i = 1; i < degrees.size(); ++i) if (degrees[i] == n - 1) return i; return -1; } // Returns true if each node rooted at u is connected to all of its ancestors. bool dfs(const unordered_map>& graph, int u, vector& degrees, vector>& connected, vector&& ancestors, vector&& seen) { seen[u] = true; for (const int ancestor : ancestors) if (!connected[u][ancestor]) return false; ancestors.push_back(u); for (const int v : graph.at(u)) { if (seen[v]) continue; // We can swap u with v, so there are more than one way. if (degrees[v] == degrees[u]) hasMoreThanOneWay = true; if (!dfs(graph, v, degrees, connected, move(ancestors), move(seen))) return false; } ancestors.pop_back(); return true; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 class Solution { public int checkWays(int[][] pairs) { final int kMax = 501; Map> graph = new HashMap<>(); int[] degrees = new int[kMax]; boolean[][] connected = new boolean[kMax][kMax]; for (int[] pair : pairs) { final int u = pair[0]; final int v = pair[1]; graph.putIfAbsent(u, new ArrayList<>()); graph.putIfAbsent(v, new ArrayList<>()); graph.get(u).add(v); graph.get(v).add(u); ++degrees[u]; ++degrees[v]; connected[u][v] = true; connected[v][u] = true; } // For each node, sort its children by degrees descendingly. for (final int u : graph.keySet()) graph.get(u).sort((a, b) -> Integer.compare(degrees[b], degrees[a])); final int root = getRoot(degrees, graph.keySet().size()); if (root == -1) return 0; if (!dfs(graph, root, degrees, connected, new ArrayList<>(), new boolean[kMax])) return 0; return hasMoreThanOneWay ? 2 : 1; } private boolean hasMoreThanOneWay = false; // Returns the root by finding the node with a degrees equal to n - 1. private int getRoot(int[] degrees, int n) { for (int i = 1; i < degrees.length; ++i) if (degrees[i] == n - 1) return i; return -1; } // Returns true if each node rooted at u is connected to all of its ancestors. private boolean dfs(Map> graph, int u, int[] degrees, boolean[][] connected, List ancestors, boolean[] seen) { seen[u] = true; for (final int ancestor : ancestors) if (!connected[u][ancestor]) return false; ancestors.add(u); for (final int v : graph.get(u)) { if (seen[v]) continue; // We can swap u with v, so there are more than one way. if (degrees[v] == degrees[u]) hasMoreThanOneWay = true; if (!dfs(graph, v, degrees, connected, ancestors, seen)) return false; } ancestors.remove(ancestors.size() - 1); return true; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 class Solution: def checkWays(self, pairs: List[List[int]]) -> int: kMax = 501 graph = collections.defaultdict(list) degrees = [0] * kMax connected = [[False] * kMax for _ in range(kMax)] for u, v in pairs: graph[u].append(v) graph[v].append(u) degrees[u] += 1 degrees[v] += 1 connected[u][v] = True connected[v][u] = True # For each node, sort its children by degrees descendingly. for _, children in graph.items(): children.sort(key=lambda a: degrees[a], reverse=True) # Find the root with a degrees equal to n - 1. root = next((i for i, d in enumerate(degrees) if d == len(graph) - 1), -1) if root == -1: return 0 hasMoreThanOneWay = False # Returns true if each node rooted at u is connected to all of its ancestors. def dfs(u: int, ancestors: List[int], seen: List[bool]) -> bool: nonlocal hasMoreThanOneWay seen[u] = True for ancestor in ancestors: if not connected[u][ancestor]: return False ancestors.append(u) for v in graph[u]: if seen[v]: continue if degrees[v] == degrees[u]: hasMoreThanOneWay = True if not dfs(v, ancestors, seen): return False ancestors.pop() return True if not dfs(root, [], [False] * kMax): return 0 return 2 if hasMoreThanOneWay else 1