. 중복 연결

<.> 684. 중복 연결 난이도 :

중간 주제 : 깊이 우선 검색, 폭이 넓은 검색, Union Find, Graph

이 문제에서 나무는

방향이없는 그래프 로 연결되어 있고 사이클이 없습니다. 당신은 1에서 n까지의 n 노드가있는 트리로 시작된 그래프가 주어지고, 하나는 추가로 에지가 추가되었습니다. 추가 된 가장자리에는 1에서 n까지 선택된 두 개의 다른 정점이 있으며 이미 존재하는 가장자리가 아니 었습니다. 그래프는 길이 n의 배열 가장자리로 표시됩니다. 그래프에서 🎜> 및 b i return 결과 그래프가 n 노드의 트리가되도록 제거 할 수있는 가장자리 . 여러 답변이 있으면 를 반환합니다. 예 1 :

입력 : 가장자리 = [[1,2], [1,3], [2,3]]

출력 :

[2,3] 예제 2 : _{입력 : 가장자리 = [[1,2], [2,3], [3,4], [1,4], [1,5]] 출력 :} [1,4]

제약 조건 :

n == edges.length 3 & lt; = n & lt; = 1000 가장자리 [i] .length == 2 1 & lt; = a i

& lt; b

i & lt; = edges.length

a

i i

반복되는 가장자리가 없습니다. 주어진 그래프가 연결되어 있습니다

솔루션 :
• 중복 연결
문제는 그래프를 유효한 트리로 바꾸기 위해 제거 할 수있는 그래프의 모서리를 식별하도록 요청합니다. 트리는 연결되어 있고 acyclic이있는 방향이없는 그래프입니다. 우리는 트리로 시작했지만 추가 모서리를 추가하여 수정 된 그래프가 제공됩니다. 우리의 목표는이 여분의 가장자리를 찾고 반환하는 것입니다.
• 핵심 요점
그래프는

변형

및 연결 중복 가장자리를 제거한 후 결과 그래프는 사이클이 없어야합니다. 여러 유효한 솔루션의 경우 입력에

마지막

가 나타나는 가장자리를 반환해야합니다. 단일 추가 모서리로 인해 그래프가 최대 한주기를 가질 수 있습니다.

접근하다
• 접근 방식은 깊이 우선 검색 (dfs)을 사용하여 사이클을 감지하는 것과 관련이 있습니다.
• 인접력 목록 표현 :
  인접성 목록을 사용하여 그래프를 나타냅니다. 이 구조는 DFS를 효율적으로 수행하는 데 적합합니다
dfs를 통한 사이클 감지 :

그래프에 가장자리를 추가하기 전에 DFS를 사용하여 모서리의 두 정점 사이에 이미 경로가 있는지 확인하십시오. 있다면이 가장자리를 추가하면 사이클이 형성됩니다.

• 가장자리를 반환 :
주기가 감지되면 현재 모서리를 중복 연결로 반환합니다.

• 계획

  입력 가장자리를 구문 분석합니다 그래프의 연결을 동적으로 추적하기 위해 인접력 목록을 유지합니다. 각 가장자리에 대해 <:> :
  재귀 DFS 함수를 사용하여 두 정점 사이에 경로가 있는지 확인하십시오. 경로가 존재하면 중복 연결로 에지를 반환합니다.
  • 그렇지 않으면 인접성 목록에 가장자리를 추가하십시오
  중복 가장자리가 발견되지 않으면 빈 결과를 반환합니다 (문제 제약에 따라 발생하지는 않지만).
PHP 에서이 솔루션을 구현합시다 : 684. 중복 연결
설명:
dfs 구현
3. :
   하나의 노드에서 시작하여 이웃을 재귀 적으로 방문하십시오 방문 된 배열을 사용하여 노드를 다시 방문하지 마십시오 트래버스 중에 대상 노드에 도달하면 경로가 존재합니다.
   • 가장자리 추가
   :
   • 가장자리의 정점 사이에 경로가 없으면 가장자리를 인접한 목록에 추가하고 다음 가장자리로 진행하십시오.
중복 가장자리
4. :
경로가 이미 존재하면 사이클을 형성 할 때 현재 가장자리를 반환합니다.

예제 연습


Example 1:

<?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]
?>

입력 : 가장자리 = [[1, 2], [1, 3], [2, 3]] 단계 :
인접성 목록을 [] 가장자리를 처리하십시오.
1. 추가 [1, 2] → 그래프 : {1 : [2], 2 : [1]}

   추가 [1, 3] → 그래프 : {1 : [2, 3], 2 : [1], 3 : [1]} 체크 [2, 3] : DFS는 경로를 찾습니다 → return [2, 3].

   출력
   • : [2, 3]
   Example 2:
   입력 : 가장자리 = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
단계

: 인접성 목록을 [] 가장자리를 처리하십시오.

추가 [1, 2] → 그래프 : {1 : [2], 2 : [1]}

추가 [2, 3] → 그래프 : {1 : [2], 2 : [1, 3], 3 : [2]} 추가 [3, 4] → 그래프 : {1 : [2], 2 : [1, 3], 3 : [2, 4], 4 : [3]} 확인 [1, 4] : DFS는 경로를 찾습니다 → return [1, 4].

출력 : [1, 4]

시간 복잡성

dfs Traversal

:

각 가장자리마다 연결을 확인하기 위해 DFS를 수행합니다.
• 최악의 경우 :
o (v e)
• , 여기서 는 정점의 수이고 e 는 가장자리의 수입니다 총 복잡성 : 우리는 모든 에지에 대해 dfs를 수행하기 때문에 전체 복잡성은 o (e × (v e))

. 입니다.

공간 복잡성 : 인접성 목록 :

o (v e)

• 방문 배열 : o (v) 총 :
o (v e)

.

예제의 출력

Example 1:
• 입력 : [[1, 2], [1, 3], [2, 3]] 출력 : [2, 3]
Example 2:
• 입력 : [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] output
: [1, 4] 주기를 감지하기 위해 dfs 기반 접근법을 사용하여 문제를 효율적으로 해결할 수 있습니다. 이 방법은 그래프를 동적으로 빌드하고 각 단계에서 중복 가장자리를 확인합니다. 솔루션은 문제 제약 조건을 준수하여 정확성을 보장하고 사이클을 형성하고 입력에서 마지막으로 발생하는 가장자리를 출력합니다.
• 연락처 링크 이 시리즈가 도움이된다면 리포지토리 Github에 별을 주거나 좋아하는 소셜 네트워크에서 게시물을 공유하는 것이 무엇입니까? 당신의 지원은 나에게 큰 의미가 있습니다! 이와 같은 유용한 콘텐츠를 원한다면 언제든지 나를 따르십시오 : LinkedIn

github

위 내용은 . 중복 연결의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!