前往
大廳
主題

LeetCode - 2360. Longest Cycle in a Graph 解題心得

Not In My Back Yard | 2023-06-18 12:00:01 | 巴幣 0 | 人氣 122

題目連結:


題目意譯:
你被給定一個有著編號為 0 到 n - 1 的 n 個節點之有向圖,其中每個節點有最多一個向外的邊。

該圖以一個給定的索引值從 0 開始且大小為 n 的之陣列 edges,代表著存在一條邊從節點 i 到節點 edges[i]。如果節點 i 沒有往外的邊,則 edges[i] == -1。

回傳圖中最長的環之長度。如果沒有環存在,則回傳 -1。

一個環為開始和結束為同一個節點的路徑。

限制:
n == edges.length
2 ≦ n ≦ 10 ^ 5
-1 ≦ edges[i] < n
edges[i] != i



範例測資:
範例 1:
輸入: edges = [3,3,4,2,3]
輸出: 3
解釋: 圖中最長的環為:2 -> 4 -> 3 -> 2。
這個環的長度為 3,所以我們回傳 3。

範例 2:
輸入: edges = [2,-1,3,1]
輸出: -1
解釋: 這個圖沒有環存在。


解題思維:
又一題少數深度優先搜尋(Depth First Search,DFS)和廣度優先搜尋(Breadth First Search,BFS)的探訪順序會長一模一樣的題目。

就是直接掃過每個節點,每當遇到一個還沒看過的節點就根據 edges 來一直走到新的節點直到走到不能在走(即該節點沒有往外的邊)、走到先前幾輪走到的節點(不含現在這一輪)或是走到現在這輪已經走過的節點。

至於把後面兩種情況分開是因為如果不管先前有沒有看到環,再看一次也沒有意義;而當現在走回到這輪已經看過的節點代表著我們現在看到了一個新的環,因此要判斷其長度(可以在探訪的過程為每個節點賦予一個時間戳記,走到相同的節點時把現在看到的時間點減去先前看到的時間點即是環的長度)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作