General Tree Traversal¶
Table of Contents¶
- 2368. Reachable Nodes With Restrictions (Medium)
- 1466. Reorder Routes to Make All Paths Lead to the City Zero (Medium)
- 582. Kill Process (Medium) 👑
2368. Reachable Nodes With Restrictions¶
-
Tags: Array, Hash Table, Tree, Depth First Search, Breadth First Search, Union Find, Graph
1466. Reorder Routes to Make All Paths Lead to the City Zero¶
"""
- 
"""
from collections import defaultdict, deque
from typing import List
# BFS
def minReorderBFS(n: int, connections: List[List[int]]) -> int:
graph = defaultdict(list)
for u, v in connections:
graph[u].append((v, 1)) # go
graph[v].append((u, 0)) # come
changes = 0
q = deque([(0, -1)])
while q:
n1, d1 = q.popleft()
for n2, d2 in graph[n1]:
if n2 != d1:
changes += d2
q.append((n2, n1))
return changes
# DFS
def minReorderDFS(n: int, connections: List[List[int]]) -> int:
graph = defaultdict(list)
for u, v in connections:
graph[u].append((v, 1)) # go
graph[v].append((u, 0)) # come
def dfs(n1, d1):
changes = 0
for n2, d2 in graph[n1]:
if n2 != d1:
changes += d2 + dfs(n2, n1)
return changes
return dfs(0, -1)
n = 5
connections = [[1, 0], [1, 2], [3, 2], [3, 4]]
print(minReorderBFS(n, connections)) # 2
print(minReorderDFS(n, connections)) # 2
582. Kill Process¶
from collections import defaultdict, deque
from typing import List
# BFS
def killProcess(pid: List[int], ppid: List[int], kill: int) -> List[int]:
graph = defaultdict(list)
for u, v in zip(ppid, pid):
graph[u].append(v)
q = deque([kill])
res = []
while q:
cur = q.popleft()
res.append(cur)
for nxt in graph[cur]:
q.append(nxt)
return res
if __name__ == "__main__":
pid = [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
assert killProcess(pid, ppid, kill) == [5, 10]