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

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

題目描述

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

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

圖用一個(gè)大小為n下標(biāo)從0開始的數(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

解釋：圖中的最長(zhǎng)環(huán)是：2-4-3-2。

這個(gè)環(huán)的長(zhǎng)度為3，所以返回3。

示例2：

輸入：edges=[2,-1,3,1]

輸出：-1

解釋：圖中沒(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è)被遍歷到的，那么我們只需記錄本輪開始節(jié)點(diǎn)的時(shí)間戳，當(dāng)遇到已經(jīng)遍歷過(guò)的節(jié)點(diǎn)時(shí)判斷該節(jié)點(diǎn)的時(shí)間戳與本輪開始節(jié)點(diǎn)的時(shí)間戳大小關(guān)系即可：

如果大于等于本輪開始節(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ù)?？臻g復(fù)雜度：O(n)。

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

classSolution{

public:

intlongestCycle(vectorintedges){

intn=edges.size();

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

intmp[n];

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

intans=-1;

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

intk=1;

for(inti=0;ii++){

//從沒(méi)有遍歷過(guò)的點(diǎn)作為起點(diǎn)

if(mp[i]==0){

intt=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!=-1mp[t]=mp[i]){

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

returnans;

總結(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è)前提