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

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

題目描述

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

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

圖用一個大小為n下標從0開始的數(shù)組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é)點至多有一條出邊。

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

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

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

解題思路分析

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

具體實現(xiàn)

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

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

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

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

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

復雜度分析

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

代碼實現(xiàn)

classSolution{

public:

intlongestCycle(vectorintedges){

intn=edges.size();

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

intmp[n];

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

intans=-1;

//k進行計數(shù)

intk=1;

for(inti=0;ii++){

//從沒有遍歷過的點作為起點

if(mp[i]==0){

intt=i;

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

while(mp[t]==0){

mp[t]=k++;

t=edges[t];

if(t==-1)break;

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

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

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

returnans;

總結(jié)

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