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]] >输出：

>约束：
• >
n == edge.length
• 3
edges [i] .length == 2

1 i i

i
• a
• i
！= b
• i
• > _{没有重复的边缘。给定的图是连接的。}
• _{解决方案：}
冗余连接
• 问题要求我们确定图形中的边缘，可以将图形转换为有效的树。树是连接和无环的无向图。给我们一个图形，该图是从树开始的，但通过添加一个额外的边缘进行了修改。我们的目标是找到并返回这个额外的优势。
>
• 关键点

该图是未取向

删除冗余边缘后所得的图形必须没有周期。 答案应返回输入中出现的

的边缘，如果有多个有效的解决方案。

1. 方法 该方法涉及使用>深度优先搜索（dfs）来检测周期：
3. >邻接列表表示：
4. >使用邻接列表来表示图形。该结构适合有效地执行df。

通过dfs

循环检测：> 在将边缘添加到图表之前，请使用dfs检查边缘两个顶点之间是否已经有一个路径。如果有的话，添加此边缘将形成一个周期。

1. 返回边缘：

   • 如果检测到一个周期，请返回当前边缘作为冗余连接。
2. 计划

   解析输入边缘。

   维护一个邻接列表以动态跟踪图形的连接。
   • 对于每个边缘：
   使用递归dfs函数检查两个顶点之间的路径是否存在。
3. 如果存在路径，请返回边缘作为冗余连接。

   否则，将边缘添加到邻接列表中。

   如果找不到冗余边缘，则返回空结果（尽管这不会按照问题的限制发生）。
   >让我们在php中实现此解决方案： 684。冗余连接

<?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)) . "
"; // Output: [2,3]
print_r(findRedundantConnection($edges2)) . "
"; // Output: [1,4]
?>

本文地址：http://letuie.cn