收斂迷宮：最大週期

Question

這個問題在一次採訪中被問到，我仍然在尋找最佳解決方案。

給你一個N細胞的迷宮。每個單元可能有多個入口點但不超過一個出口 （即入口/出口點是單向門，如閥門）。

使用從0 到N-1的整數值命名單元格。

你需要找到迷宮中最大週期的長度。如果沒有循環，則返回-1。

INPUT FORMAT

• 第一行具有N
• 第二線具有邊緣[]陣列的N個值的列表中的小區的數目。 edge [i]包含單元格'i'可以在一個步驟中從 到達的單元格編號。如果'我的細胞沒有退出，邊緣[i]爲-1。

OUTPUT FORMAT

• 長度最大週期。

樣品輸入：

4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21

樣本輸出

我已經試圖用DFS做到這一點，以找到所有可能的週期和打印最大的週期大小。 請讓我知道是否有更好的解決方案。

Answer 1

給定圖中的一個節點，從它開始有一個唯一的最大路徑（因爲最多隻有一個節點出口）。它可能會或可能不會循環。

很容易找到從節點開始的最終週期長度：保持以下出口節點，沿着路徑記錄集合中的節點。當你找不到任何退出節點，或者你即將訪問一個先前訪問過的節點時停止。如果沒有出口節點，則不存在循環，否則可以從先前訪問的節點開始查找循環長度，並重新跟蹤循環。 [你也可以在這裏使用Floyd算法，這需要O（1）而不是O（N）存儲，但是我們將在下一步中使用O（N）存儲]。

使用此方法，可以找到O（N）時間中的最大週期：對圖中每個節點重複上述算法，但緩存結果（如果沒有找到週期，則存儲-1）。如果在路徑中找到先前緩存的結果，則必須小心地停止上面的循環查找，並且一旦找到節點的結果，就必須緩存路徑上所有節點的結果，直到找到節點誰的結果已被緩存。最大週期的大小是最大緩存值的大小。

這是O（N）運行時：每個邊（其中至多N個）在圖中至多跟隨3次，並且對於圖中的每個節點高速緩存只更新一次。它使用O（N）附加存儲。

Answer 2

以下是JavaScript中的一個實現。我沒有使用JavaScript的任何奇特功能，因此可以從代碼中很容易地看到該算法。在另一方面，它確實需要ES6支持運行（IE忘了）：

function largestCycle(edges) { 
 
    var result, visitedFrom, startCell, cell, cells; 
 
    
 
    result = []; 
 
    visitedFrom = Array(edges.length).fill(-1); 
 
    for (startCell = 0; startCell < edges.length; startCell++) { 
 
     cells = []; 
 
     for (cell=startCell; cell>-1 && visitedFrom[cell]===-1; cell = edges[cell]) { 
 
      visitedFrom[cell] = startCell; 
 
      cells.push(cell); 
 
     } 
 
     if (cell > -1 && visitedFrom[cell] === startCell) { 
 
      cells = cells.slice(cells.indexOf(cell)); 
 
      if (cells.length > result.length) result = cells; 
 
     } 
 
    } 
 
    return result; 
 
} 
 

 
// Snippet I/O 
 

 
var input = document.querySelector('textarea'); 
 
var output = document.querySelector('span'); 
 

 
(input.oninput = function() { 
 
    // Get input as array of numbers 
 
    var edges = input.value.trim().split(/\s+/).map(Number); 
 
    // Apply algorithm 
 
    var cycle = largestCycle(edges); 
 
    // Output result 
 
    output.textContent = cycle.length + ': ' + JSON.stringify(cycle); 
 
})(); // Execute also at page load

Input:<br> 
 
<textarea style="width:100%">4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21</textarea><br> 
 
Greatest Cycle: <span></span>

這個運行在爲O（n）。即使外層循環同時具有嵌套循環和遍歷數組的表達式（使用slice和indexOf），但這些子迭代僅在每個單元中執行一次，因此總共仍然是O（n）。

該函數不僅返回週期大小，而且還包含包含屬於該週期的單元列表的數組。這是一個小開銷，但可以更好地驗證結果。

Answer 3

import java.util.Scanner; 
class path 
{ 
public static void main(String [] args) 
{ 
    Scanner scnr=new Scanner(System.in); 
    int n=scnr.nextInt(); 
    int a[]=new int[n]; 
    for(int i=0;i<n;i++) 
    { 
     a[i]=scnr.nextInt(); 
    } 
    int path=-1; 

    int j; 
    for(int i=0;i<n;i++) 
    { j=i; 
     int count=0; 
     while(true) 
     { 
      count++; 
      if(a[j]==-1) 
      { 
       break; 
      } 
      else if(i==a[j]) 
      { 
       if(count>path) 
       path=count; 
       break; 
      } 
      else 
      { int temp=j; 
       j=a[j]; 
       a[temp]=-1;     
      } 
     } 
    } 
    System.out.println("my path: "+path); 
} 

}