題目鏈接：2716. 食物鏈 - AcWing題庫
首先我們浏覽題目 能得到一個很重要的線索：這是一張拓撲圖 即點與點之間存在拓撲關系
所以我們很自然的能想到使用記憶化搜素，至於原因請參考這篇博客：藍橋杯/洛谷 ： 最長滑雪道/滑雪 + 擴展題目（記憶化搜索 Python）_KS想去海底的博客-CSDN博客d問題描述 小袁非常喜歡滑雪， 因為滑雪很刺激。為了獲得速度，滑的區域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你。 小袁想知道在某個區域中最長的一個滑坡。區域由一個二維數組給出。數組的每個數字代表點的高度。如下： 一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當然25-24-23-...-3-2-1更長。事實上，這是最長的一條。 你的任務就是找到最長的一條滑坡，並且將滑坡的長度輸出。 滑
https://blog.csdn.net/m0_54689021/article/details/125457728?spm=1001.2014.3001.5501大體使用什麼算法已經定下來了，接下來應該扣細節了。
我們可以想一下，怎樣才能算作一條食物鏈，是不是一條從起點能走向終點的路徑？
所以我們可以維護一個dp數組，數組儲存從這個點出發（不一定是起點），有幾條路徑能走到終點。
那麼起點和終點怎麼判斷呢，這裡就需要用到拓撲排序中的術語了：起點（入度為0）
終點（出度為0）
確定起點和終點之後 就需要思考這個搜索函數dfs該怎麼寫了。首先我們可以先思考終點前的一個點，這個點的dp數組值是不是就應該是它連接著幾個終點？比如A B都是終點 然後點C->A C->B 有這兩條路徑，那麼dp[C]=2 。
這樣以此類推， 能通向C的點D就加上dp[C]的值 和 從點D能到達的點的dp值，如此往復遞歸直到起點。
需要注意的是，如果一個點已經被遍歷過了，那麼它的dp值就不會再被改變了，因為它的dp值只能被該點的下一個點更改。由於拓撲序的關系，該點之後的點不可能再被遍歷到，因此該點的dp值不會再被改變。
上代碼～
import sys
sys.setrecursionlimit(1000000) # 修改遞歸深度 其他語言可以忽略
n,m = map(int,input().split())
Map = [dict() for i in range(n+1)]
din = [0 for i in range(n+1)] # 每個點的入度
dout = [0 for i in range(n+1)] # 每個點的出度
for i in range(m) :
a,b = map(int,input().split())
din[b] += 1 ; dout[a] += 1
Map[a][b] = 1
ST = [] ; EN = [] # 起點 終點
for i in range(1,n+1) :
if din[i] == 0 : ST.append(i)
elif dout[i] == 0 : EN.append(i)
dp = [-1 for i in range(n+1)] # 初始化為-1
def dfs(node) :
global dp
if dp[node] != -1 : # 如果被遍歷過直接返回
return dp[node]
if node in EN : return 1 # 如果是終點返回 1
dp[node] = 0
for next in Map[node].keys() : # 否則累加該點能到的所有點的dp值
dp[node] += dfs(next)
return dp[node] # 返回
ans = 0
for i in ST : dfs(i) ; ans += dp[i] # 從每個起點開始走 累加答案
print(ans)
如有疑問 歡迎留言討論 ～
