C C++ 題解LeetCode2360圖中的最長環(huán)示例

更新時間：2022年10月18日 16:21:04 作者：Junkman丶

這篇文章主要為大家介紹了C C++ 題解LeetCode2360圖中的最長環(huán)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目描述

題目鏈接：2360. 圖中的最長環(huán)

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

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

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

一個環(huán)指的是起點和終點是 同一個 節(jié)點的路徑。

提示:

示例 1：

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

示例 2：

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

整理題意

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

給定一個整數數組 edges，表示節(jié)點 i 到節(jié)點 edges[i] 之間有一條有向邊（ i 指向 edges[i]）。

規(guī)定如果節(jié)點 i 沒有出邊，那么 edges[i] == -1 。

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

解題思路分析

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

具體實現

那么我們要怎么記錄遍歷過的節(jié)點是否為本輪遍歷過的節(jié)點呢？

很容易想到每次都清空一遍標記數組，但是因為題目數據范圍的原因，這樣做是會超時的。

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

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

初始化環(huán)的最大值為 -1，期間不斷維護環(huán)的最大值即可，最后返回這個最大值即可。

復雜度分析

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

代碼實現

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        // mp[i] = j 表示節(jié)點 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;
                // 找到第一個遍歷過的節(jié)點
                while(mp[t] == 0){
                    mp[t] = k++;
                    t = edges[t];
                    if(t == -1) break;
                }
                // 利用時間戳計算環(huán)的長度，取最大值
                if(t != -1 && mp[t] >= mp[i]){
                    ans = max(ans, k - mp[t]);
                }
            }
        }
        return ans;
    }
};