LeetCode 解題紀錄 1557. Minimum Number of Vertices to Reach All Nodes
Oct 14, 2022
題目
在一個有向無迴圈的圖中，找出端點的最小集合，只要透從這些端點開始走一遍就能到達所有的端點(開始的端點也算在內)
限制條件
- 端點數目從 0 到 n-1
- 路徑不會重複，數目為 1 ~ 100000
觀察
- 如果有個端點只有往外連接，沒有進入的連接，那它一定是這個集合的一部份，因為它如果不當成一個起點，那就沒有連接到它的路徑了
- 如果有個端點有進入的連接，那它一定不是集合的一部分，因為我只要選它的上個端點即可
思路
- 使用一個長度為 n 的矩陣來紀錄進入連接
- 透過檢查每個路徑的終點端點，在陣列上幫它加 1 就是進入連接的數目了
- 拜訪過所有的路徑後，將進入連接為 0 的端點加入集合
Trial 1
結果
時間與空間複雜度皆為 O(n) ，結果沒有很好，去看看別人怎麼寫的，觀念是一樣的但發現有點可以改進的小地方
Trail 2
- 我們並不需要知道準確的 in degree 是多少，只要知道為 0 的即可，所以不要做 + 1的運算，直接設成 1 即可
結果
時間與空間複雜度還是 O(n)，但執行時間減少不少，用最精簡的動作達成需求是最佳化的必經過程
