直接用一般的 DFS 把每個節點跑一遍會吃 TLE,所以要進行剪枝,
因為每個節點都只會單向的指向一個目標,所以節點間的連線圖都會形成一個環,
假設 1 會到 2,由 1 開始 DFS 的節點連接數是 n,那 2 開始 DFS 的節點連接數會是 n-1
因此在每一次 DFS 後,都不需要再去 DFS 先前跑過的節點,因為節點連接數一定比較少,而這就是這題的剪枝方法了
重新修改一下前面有講錯的部分
直接用一般的 DFS 把每個節點跑一遍會吃 TLE,所以要進行剪枝,
因為每個節點都只會單向的指向一個目標,所以節點間的連線圖都會形成一個環,
假設 1 會到 2,由 1 開始 DFS 的節點連接數是 n,那 2 開始 DFS 的節點連接數會是小於或等於 n 的數
因此在每一次 DFS 後,都不需要再去 DFS 先前跑過的節點,因為節點連接數一定比較少或是一樣,這題只需要找最大的節點連接數
這樣就可以減少 DFS 的次數了