Approach
Depth-first search
For Number Of Ways To Reconstruct A Tree, the implementation follows one branch at a time, making it suitable for components, trees, backtracking, or dependency exploration.
- Define the state carried into one recursive or stack frame.
- Mark or choose the current state before exploring children.
- Combine child results or undo the choice when the branch finishes.
Code notes
- 51 lines of Python from the credited upstream file 1719.py.
- The implementation visibly relies on sequence storage, hash lookup.
- No explicit loop blocks detected, together with recursive traversal.
Complexity
Count unique states for graph traversal; for backtracking, count the branching factor and maximum depth.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution:2 def checkWays(self, pairs: list[list[int]]) -> int:3 MAX = 5014 graph = collections.defaultdict(list)5 degrees = [0] * MAX6 connected = [[False] * MAX for _ in range(MAX)]7 8 for u, v in pairs:9 graph[u].append(v)10 graph[v].append(u)11 degrees[u] += 112 degrees[v] += 113 connected[u][v] = True14 connected[v][u] = True15 16 17 for _, children in graph.items():18 children.sort(key=lambda x: -degrees[x])19 20 21 root = next((i for i, d in enumerate(degrees) if d == len(graph) - 1), -1)22 if root == -1:23 return 024 25 hasMoreThanOneWay = False26 27 def dfs(u: int, ancestors: list[int], seen: list[bool]) -> bool:28 """29 Returns True if each node rooted at u is connected to all of its30 ancestors.31 """32 nonlocal hasMoreThanOneWay33 seen[u] = True34 for ancestor in ancestors:35 if not connected[u][ancestor]:36 return False37 ancestors.append(u)38 for v in graph[u]:39 if seen[v]:40 continue41 if degrees[v] == degrees[u]:42 hasMoreThanOneWay = True43 if not dfs(v, ancestors, seen):44 return False45 ancestors.pop()46 return True47 48 if not dfs(root, [], [False] * MAX):49 return 050 return 2 if hasMoreThanOneWay else 151