快捷導(dǎo)航

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

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

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

題目描述

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

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

請(qǐng)你返回圖中的 最長(zhǎng) 環(huán)，如果沒(méi)有任何環(huán)，請(qǐng)返回 -1 。

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

提示:

示例 1：

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

示例 2：

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

整理題意

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

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

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

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

解題思路分析

因?yàn)樵擃}所給的圖為有向圖，且每個(gè)節(jié)點(diǎn)至多只有一條出邊，我們可以從任意一個(gè)節(jié)點(diǎn)出發(fā)，如果能夠到達(dá) 本輪已經(jīng)遍歷過(guò)的節(jié)點(diǎn)，那么說(shuō)明能夠構(gòu)成一個(gè)新環(huán)。維護(hù)環(huán)的最大值即可。

具體實(shí)現(xiàn)

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

很容易想到每次都清空一遍標(biāo)記數(shù)組，但是因?yàn)轭}目數(shù)據(jù)范圍的原因，這樣做是會(huì)超時(shí)的。

正確做法：利用一個(gè)時(shí)間戳來(lái)表示每個(gè)節(jié)點(diǎn)是第幾個(gè)被遍歷到的，那么我們只需記錄本輪開(kāi)始節(jié)點(diǎn)的時(shí)間戳，當(dāng)遇到已經(jīng)遍歷過(guò)的節(jié)點(diǎn)時(shí)判斷該節(jié)點(diǎn)的時(shí)間戳與本輪開(kāi)始節(jié)點(diǎn)的時(shí)間戳大小關(guān)系即可：

如果大于等于本輪開(kāi)始節(jié)點(diǎn)的時(shí)間戳：說(shuō)明是本輪遍歷到新的一個(gè)環(huán)；
否則僅僅表示遍歷到之前遍歷過(guò)的節(jié)點(diǎn)，沒(méi)有構(gòu)成新的環(huán)（因?yàn)橹氨闅v過(guò)的節(jié)點(diǎn)如果有環(huán)也已經(jīng)記錄過(guò)了）

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

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n)，其中 n 為 edges 的長(zhǎng)度，也就是點(diǎn)的個(gè)數(shù)。
空間復(fù)雜度：O(n)。

代碼實(shí)現(xiàn)

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

總結(jié)

該題的核心思想為記錄每個(gè)節(jié)點(diǎn)被遍歷到的時(shí)間戳，通過(guò) 時(shí)間戳來(lái)實(shí)現(xiàn)找新環(huán)的邏輯。
因?yàn)槭怯邢驁D且每個(gè)節(jié)點(diǎn)至多有一個(gè)出度，所以可以利用時(shí)間戳的方式來(lái)實(shí)現(xiàn)，需要注意這個(gè)前提條件。

測(cè)試結(jié)果：