。冗余连接-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]
?>

登录后复制