。冗長接続

684。冗長接続

難易度： medium

トピック：深さ第一検索、幅広い最初の検索、ユニオンファインド、グラフ

この問題では、ツリーは接続されていてサイクルがない

1からNにラベル付けされたnノードを備えたツリーとして始まり、1つのエッジが追加されたグラフが与えられます。追加されたエッジには、1からnまで選択された2つの>異なる

頂点があり、すでに存在していたエッジではありませんでした。グラフは、長さnの配列エッジとして表されます。ここでは、エッジ[i] = [a

i、bi_{]は、ノードa} i およびb _i。 結果のグラフがnノードのツリーになるように削除できるエッジを返します

。複数の回答がある場合は、

を返します 例1：

input：

edges = [[1,2]、[1,3]、[2,3]]

• output：[2,3]
• 例2：

input：

edges = [[1,2]、[2,3]、[3,4]、[1,5]、[1,5]]

• output：[1,4]
• 制約：

n == edges.length

3＆lt; = n＆lt; = 1000

• edges [i] .length == 2
• 1＆lt; = a
i
• ＆lt; b
i
• ＆lt; = edges.length a _i ！= b
i
• 繰り返しエッジはありません。 指定されたグラフが接続されています。
• 解決策：

問題は、グラフのエッジを削除してグラフを有効なツリーに変えることができるエッジを識別するよう求めます。ツリーは、接続された非環状の無向グラフです。ツリーとして始まったが、1つの余分なエッジを追加することで変更されたグラフが与えられました。私たちの目標は、この余分なエッジを見つけて返すことです。 キーポイント

グラフは冗長エッジを削除した後の結果のグラフにはサイクルがない必要があります。

答えは、複数の有効なソリューションの場合、入力で最後に表示されるエッジを返す必要があります。

グラフは、単一の余分なエッジのためにせいぜい1つのサイクルを持つことができます。

1. アプローチ アプローチには、サイクルを検出するために深度検索（dfs）を使用することが含まれます。
3. 隣接リスト表現：
   • 隣接リストを使用してグラフを表します。この構造は、DFSを効率的に実行するのに適しています

4. dfs ：経由のサイクル検出

   グラフにエッジを追加する前に、DFSを使用して、エッジの2つの頂点の間に既にパスがあるかどうかを確認します。ある場合、このエッジを追加するとサイクルが形成されます。
5. エッジを返します

   ：

   サイクルが検出された場合は、現在のエッジを冗長接続として返します。
プラン

入力エッジを解析します。

1. グラフの接続を動的に追跡するために隣接リストを維持します。 各エッジについて：
2. 再帰的なDFS関数を使用して、2つの頂点の間にパスが存在するかどうかを確認します。
パスが存在する場合は、冗長接続としてエッジを返します。
3. それ以外の場合は、隣接リストにエッジを追加します。
   • 冗長なエッジが見つからない場合は空の結果を返します（ただし、これは問題の制約に従って発生しません）。
   • このソリューションをPHP：
   684に実装しましょう。冗長接続

説明：

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

：

1つのノードから始めて、隣人を再帰的に訪問します
1. 訪問された配列を使用して、ノードの再訪を避けます

   トラバーサル中にターゲットノードに到達した場合、パスが存在します。

   • エッジの追加
   ：
   • エッジの頂点の間にパスが存在しない場合、隣接リストにエッジを追加して、次のエッジに進みます。

2. 冗長エッジ：

   既に存在する場合、サイクルを形成するため、パスを現在のエッジを返します。
3. 例のウォークスルー

   例1：

   input
   • ：edges = [[1、2]、[1、3]、[2、3]]
手順

：

隣接リストを[]。

として初期化します

エッジを処理します： [1、2]→グラフを追加：{1：[2]、2：[1]}

[1、3]→グラフを追加：{1：[2、3]、2：[1]、3：[1]} チェック[2、3]：dfsはパスを見つけます→[2、3]。

2. output
   • ：[2、3]
   • 例2：
   • input
   ：edges = [[1、2]、[2、3]、[3、4]、[1、4]、[1、5]]

手順：

隣接リストを[]。

として初期化します

エッジを処理します： [1、2]→グラフを追加：{1：[2]、2：[1]}

add [2、3]→グラフ：{1：[2]、2：[1、3]、3：[2]}

add [3、4]→グラフ：{1：[2]、2：[1、3]、3：[2、4]、4：[3]} check [1、4]：dfsはパスを見つけます→[1、4]。

2. output
   • ：[1、4]
   • 時間の複雑さ
   • dfsトラバーサル
   ：

• 各エッジについて、DFSを実行して接続を確認します。
最悪のケース：
• o（v e）、ここで、vは頂点の数とeです。 はエッジの数です。

完全な複雑さ：

すべてのエッジに対してDFSを実行するため、全体的な複雑さは
• o（e×（v e））。です。

スペースの複雑さ：

隣接するリスト：
• o（v e）。
訪問アレイ：
• o（v）。
合計：
• o（v e）。

例の出力

例1：

input：[[1、2]、[1、3]、[2、3]]

output：[2、3]

例2：

input：[[1、2]、[2、3]、[3、4]、[1、4]、[1、5]]

output ：[1、4]

dfsベースのアプローチを使用して、サイクルを検出するために問題を効率的に解決できます。このメソッドはグラフを動的に構築し、各ステップで冗長エッジをチェックします。このソリューションは、問題の制約を順守し、サイクルを形成し、入力で最後に発生するエッジを出力することにより、正確性を保証します。

連絡先リンク

このシリーズが役立つと思った場合は、リポジトリをGithubでスター

に提供するか、お気に入りのソーシャルネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味があります！

このようなもっと役立つコンテンツが必要な場合は、お気軽にフォローしてください：

linkedIn

• github

以上が。冗長接続の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。