參考題目：所有可達(dá)路徑

題目描述

????????給定一個(gè)有 n 個(gè)節(jié)點(diǎn)的有向無環(huán)圖，節(jié)點(diǎn)編號(hào)從 1 到 n。請(qǐng)編寫一個(gè)函數(shù)，找出并返回所有從節(jié)點(diǎn) 1 到節(jié)點(diǎn) n 的路徑。每條路徑應(yīng)以節(jié)點(diǎn)編號(hào)的列表形式表示。

輸入描述

第一行包含兩個(gè)整數(shù) N，M，表示圖中擁有 N 個(gè)節(jié)點(diǎn)，M 條邊

后續(xù) M 行，每行包含兩個(gè)整數(shù) s 和 t，表示圖中的 s 節(jié)點(diǎn)與 t 節(jié)點(diǎn)中有一條路徑

輸出描述

輸出所有的可達(dá)路徑，路徑中所有節(jié)點(diǎn)之間空格隔開，每條路徑獨(dú)占一行，存在多條路徑，路徑輸出的順序可任意。如果不存在任何一條路徑，則輸出 -1。

注意輸出的序列中，最后一個(gè)節(jié)點(diǎn)后面沒有空格！?例如正確的答案是 `1 3 5`,而不是 `1 3 5 `， 5后面沒有空格！

輸入示例

5 5
1 3
3 5
1 2
2 4
4 5

輸出示例

1 3 5
1 2 4 5

提示信息

用例解釋：

有五個(gè)節(jié)點(diǎn)，其中的從 1 到達(dá) 5 的路徑有兩個(gè)，分別是 1 -> 3 -> 5 和 1 -> 2 -> 4 -> 5。

因?yàn)閾碛卸鄺l路徑，所以輸出結(jié)果為：

1 3 5
1 2 4 5

或

1 2 4 5
1 3 5
都算正確。

數(shù)據(jù)范圍：

• 圖中不存在自環(huán)
• 圖中不存在平行邊
• 1 <= N <= 100
• 1 <= M <= 500

問題分析：這個(gè)很明細(xì)使用的是dfs（深度優(yōu)先搜索）的框架代碼，什么叫做深度優(yōu)先搜索算法呢？就是一路走到底，直到無路可走的時(shí)候，就回退，尋找其它的出路，存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)可以使用鄰接表、鄰接矩陣的等等，如果還是不太理解：代碼隨想錄

n, m = map(int, input().split())
Map = [[] for _ in range(n + 1)]for _ in range(m):a, b = map(int, input().split())Map[a].append(b)
stack = []  
ans = []
def dfs(start, target):stack.append(start)if start == target:ans.append(stack[:])else:for next in Map[start]:dfs(next, target)stack.pop()
dfs(1, n)
if len(ans):for path in ans:path_len = len(path)for i in range(path_len):if i != path_len - 1:  # 換不換行print(f"{path[i]} ", end='')else:print(f"{path[i]}")
else:print(-1)