。冗餘連接-php教程-PHP中文網

684。冗餘連接

難度：中等

>>主題：深度優先搜索，廣度優先搜索，聯合查找，圖形

在這個問題中，一棵樹是連接且沒有循環的無向圖。 >您獲得了一個圖形，該圖是從1到n標記的n個節點開始的樹，並增加了一個邊緣。添加的邊緣具有從1到n選擇的兩個不同的

的頂點，並且不是已經存在的邊緣。該圖表示為長度為n的數組邊緣，其中邊緣[i] = [ai ，b_i]表明節點a_{i 返回_{可以刪除的邊緣，以便結果圖是N節點的樹}。如果有多個答案，請返回_在輸入。}

>示例1：

>輸入： edges = [[1,2]，[1,3]，[2,3]]

>輸出：。冗餘連接 [2,3]

>>示例2：

>輸入：

edges = [[1,2]，[2,3]，[3,4]，[1,4]，[1,5]] >輸出：

[1,4]

。冗餘連接

>
3＆lt; = n＆lt; = 1000

1＆lt; = a i＆lt; bi

＆lt; = edges.length

a
！ = b
>
沒有重複的邊緣。給定的圖是連接的。
解決方案：冗餘連接
>

該圖是

未取向和

刪除冗餘邊緣後所得的圖形必須沒有周期。 答案應返回輸入中出現的最後一個

的邊緣，如果有多個有效的解決方案。

由於單個額外的邊緣，該圖最多可以具有一個週期。

該方法涉及使用>深度優先搜索（DFS）來檢測週期：
>鄰接列表表示：

>使用鄰接列表來表示圖形。該結構適合有效地執行DF。
循環檢測：> 在將邊緣添加到圖表之前，請使用DFS檢查邊緣兩個頂點之間是否已經有一個路徑。如果有的話，添加此邊緣將形成一個週期。
返回邊緣
如果檢測到一個週期，請返回當前邊緣作為冗餘連接。
- 計劃

維護一個鄰接列表以動態跟踪圖形的連接。

對於每個邊緣：

使用遞歸DFS函數檢查兩個頂點之間的路徑是否存在。
如果存在路徑，請返回邊緣作為冗餘連接。
- 如果找不到冗餘邊緣，則返回空結果（儘管這不會按照問題的限制發生）。
解釋：

dfs實現
：

<?php /**
 * @param Integer[][] $edges
 * @return Integer[]
 */
function findRedundantConnection($edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to perform DFS and check connectivity
 *
 * @param $src
 * @param $target
 * @param $visited
 * @param $adjList
 * @return bool
 */
private function isConnected($src, $target, &$visited, &$adjList) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$edges1 = [[1,2],[1,3],[2,3]];
$edges2 = [[1,2],[2,3],[3,4],[1,4],[1,5]];

print_r(findRedundantConnection($edges1)) . "\n"; // Output: [2,3]
print_r(findRedundantConnection($edges2)) . "\n"; // Output: [1,4]
?>

登入後複製