C C++ 題解LeetCode2360圖中的最長環範例

2022-10-20 14:01:33

題目描述

題目連結：2360. 圖中的最長環

給你一個 n 個節點的 有向圖 ，節點編號為 0 到 n - 1 ，其中每個節點至多有一條出邊。

圖用一個大小為 n 下標從 0 開始的陣列 edges 表示，節點 i 到節點 edges[i] 之間有一條有向邊。如果節點 i 沒有出邊，那麼 edges[i] == -1 。

請你返回圖中的最長環，如果沒有任何環，請返回 -1 。

一個環指的是起點和終點是 同一個 節點的路徑。

提示:

範例 1：

輸入： edges = [3,3,4,2,3]
輸出去： 3
解釋：圖中的最長環是：2 -> 4 -> 3 -> 2 。
這個環的長度為 3 ，所以返回 3 。

範例 2：

輸入： edges = [2,-1,3,1]
輸出： -1
解釋：圖中沒有任何環。

整理題意

題目給定一張含有 n 個節點的 有向圖，且每個節點至多有一條出邊。

給定一個整數陣列 edges，表示節點 i 到節點 edges[i] 之間有一條有向邊（ i 指向 edges[i]）。

規定如果節點 i 沒有出邊，那麼 edges[i] == -1 。

題目讓我們返回圖中最長的環，如果圖中不存在環返回 -1 。

解題思路分析

因為該題所給的圖為有向圖，且每個節點至多隻有一條出邊，我們可以從任意一個節點出發，如果能夠到達本輪已經遍歷過的節點，那麼說明能夠構成一個新環。維護環的最大值即可。

具體實現

那麼我們要怎麼記錄遍歷過的節點是否為本輪遍歷過的節點呢？

很容易想到每次都清空一遍標記陣列，但是因為題目資料範圍的原因，這樣做是會超時的。

正確做法：利用一個時間戳來表示每個節點是第幾個被遍歷到的，那麼我們只需記錄本輪開始節點的時間戳，當遇到已經遍歷過的節點時判斷該節點的時間戳與本輪開始節點的時間戳大小關係即可：

如果大於等於本輪開始節點的時間戳：說明是本輪遍歷到新的一個環；
否則僅僅表示遍歷到之前遍歷過的節點，沒有構成新的環（因為之前遍歷過的節點如果有環也已經記錄過了）

初始化環的最大值為 -1，期間不斷維護環的最大值即可，最後返回這個最大值即可。

複雜度分析

時間複雜度：O(n)，其中 n 為 edges 的長度，也就是點的個數。
空間複雜度：O(n)。

程式碼實現

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        // mp[i] = j 表示節點 i 是第 j 個遍歷到的
        int mp[n];
        memset(mp, 0, sizeof(mp));
        int ans = -1;
        // k 進行計數
        int k = 1;
        for(int i = 0; i < n; i++){
            // 從沒有遍歷過的點作為起點
            if(mp[i] == 0){
                int t = i;
                // 找到第一個遍歷過的節點
                while(mp[t] == 0){
                    mp[t] = k++;
                    t = edges[t];
                    if(t == -1) break;
                }
                // 利用時間戳計算環的長度，取最大值
                if(t != -1 && mp[t] >= mp[i]){
                    ans = max(ans, k - mp[t]);
                }
            }
        }
        return ans;
    }
};