Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
[15-lines] Timing a single recursive DFS solution in Clear category for On the same path by Phil15
def on_same_path(tree, pairs):
"""For each given pair of tree's nodes, say if there are on a same path."""
# We note arrival/departure times of all nodes during a single DFS.
timer, intime, outtime = 0, {}, {}
def timestamp(node, times): # Note the time in `times` for the `node`.
nonlocal timer
timer += 1
times[node] = timer
def timed_dfs(root, childs): # DFS on the tree, with timestamps at each step.
timestamp(root, intime)
for child_tree in childs:
timed_dfs(*child_tree)
timestamp(root, outtime)
def is_descendant_of(desc, parent):
# Is the node `desc` a descendant of the node `parent`? It is if we
# find & quit `desc` after we find `parent` and before we quit `parent`.
return intime[parent] < intime[desc] and outtime[desc] < outtime[parent]
timed_dfs(*tree)
return [is_descendant_of(u, v) or is_descendant_of(v, u) for u, v in pairs]
Dec. 10, 2019
Comments:
