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

第CC++題解LeetCode2360圖中的最長環(huán)示例目錄題目描述整理題意解題思路分析具體實(shí)現(xiàn)復(fù)雜度分析代碼實(shí)現(xiàn)總結(jié)

題目描述

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

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

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

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

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

提示:

示例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é)點(diǎn)的有向圖，且每個節(jié)點(diǎn)至多有一條出邊。

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

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

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

解題思路分析

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

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

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

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

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

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

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

復(fù)雜度分析

時間復(fù)雜度：O(n)，其中n為edges的長度，也就是點(diǎn)的個數(shù)?？臻g復(fù)雜度：O(n)。

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

classSolution{

public:

intlongestCycle(vectorintedges){

intn=edges.size();

//mp[i]=j表示節(jié)點(diǎn)i是第j個遍歷到的

intmp[n];

memset(mp,0,sizeof(mp));

intans=-1;

//k進(jìn)行計(jì)數(shù)

intk=1;

for(inti=0;ii++){

//從沒有遍歷過的點(diǎn)作為起點(diǎn)

if(mp[i]==0){

intt=i;

//找到第一個遍歷過的節(jié)點(diǎn)

while(mp[t]==0){

mp[t]=k++;

t=edges[t];

if(t==-1)break;

//利用時間戳計(jì)算環(huán)的長度，取最大值

if(t!=-1mp[t]=mp[i]){

ans=max(ans,k-mp[t]);

returnans;

總結(jié)

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