LeetCode LCP 07. 传递信息

题目链接：LCP 07. 传递信息

Ideas

算法：深度优先搜索
数据结构：图
思路：题目中要求的是所有的方案数，自然而然的想到要用深度优先搜索DFS，通过k来控制搜索的深度即可。

Code

Python

class Solution:
	def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
		def dfs(idx, depth):
			if depth > k:
				return
			if depth == k and idx == n - 1:
				nonlocal ans
				ans += 1
			for target in adjacency.get(idx, []):
				dfs(target, depth + 1)
		
		adjacency = {
    }
		for (start, end) in relation:
			if adjacency.get(start, None):
				adjacency[start].append(end)
			else:
				adjacency[start] = [end]
		
		ans = 0
		dfs(0, 0)
		return ans