ノードをグループの最大数に分けます

2493。ノードをグループの最大数に分けます

難易度：hard

トピック：幅第一検索、Union Find、Graph

無向グラフのノードの数を表す正の整数nが与えられます。ノードのラベルは1からn。

です また、2D整数アレイエッジも与えられます。ここでは、エッジ[i] = [a

i_、bi_]は、双方向ノードの間のエッジa i_とbi _。 指定されたグラフが切断される可能性があることに注意 グラフのノードをMグループ（

1インダックス

）に分割して、次のようにしてください。 グラフ内の各ノードは、正確に1つのグループに属します。 エッジで接続されているグラフ内のノードのすべてのペア[a

i

、b
• i
]。インデックスxを使用し、b
• i_{はインデックスyのグループに属し、| y -x | = 1.} return _{ノードを分割できるグループの最大数（つまり、最大m）。 NODESを指定された条件にグループ化することが不可能な場合は、}-1 例1：

input：

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

output：

4

説明：
• 画像に示されているように： 最初のグループにノード5を追加します。
• ノード1を2番目のグループに追加します。 ノード2と4を3番目のグループに追加します。
• ノード3と6を4番目のグループに追加します。 すべてのエッジが満たされていることがわかります。
  • 5番目のグループを作成して3番目または4番目のグループからノードを移動すると、少なくともエッジの上で満たされないことが示されます。
  • 例2：
  • 入力：
  n = 3、edges = [[1,2]、[2,3]、[3,1]]

output：

-1

説明：

最初のグループにノード1を、2番目のグループにノード2を追加し、最初の2つのエッジを満たすために3番目のグループにノード3を追加すると、3番目のエッジが満たされないことがわかります。 。
• グループ化が不可能であることが示される可能性があります。
制約：
• 1＆lt; = n＆lt; = 500
  1＆lt; = edges.length＆lt; = 10
  4 edges [i] .length == 2

1＆lt; = a i、B a

i
• ！= b
i
• 頂点の任意のペアの間に最大1つのエッジがあります。
• ヒント：
  1. グラフが二部でない場合、ノードをグループ化することはできません。
  接続された各コンポーネントの問題を個別に解決できることに注意してください。最終的な答えは、各コンポーネントのグループの最大数の合計にすぎないことに注意してください。
  2. 最後に、接続された各コンポーネントの問題を解決するために、ノードVの場合、その位置を左端グループに修正すると、他のすべてのノードの位置を評価できることがわかります。その位置は、ノードv。
  でルート化した後のBFSツリーのノードの深さです。
  解決策：

  問題、

  「ノードをグループの最大数に分割する」

  には、対応のないグラフのノードを分割できるグループの最大数を決定することを伴います。 各ノードは、正確に1つのグループに属します。

  隣接するノードは、インデックスが正確に1によって異なるグループにあります。 グラフが二部でない場合、グループ化は不可能であり、関数は-1を返す必要があります。
  2. キーポイント

  グラフのプロパティ：

  グラフが切断される場合があります。
  • 検証：接続されたコンポーネントごとに、Bipartiteであるかどうかを確認します。そうでない場合は、-1。
  を返します
  • 二倍性の性質：ソリューションにはBFSが含まれ、二極性を検証します
  • 統合ファインド：接続されたコンポーネントを効率的にグループ化するのに役立ちます。
  • アプローチ

  前処理：

  1. 隣接リストを使用してグラフを表します。 組合ファインドを使用して、接続されたコンポーネントを識別します。

     • bfs bipartitenessを検証する：

  2. 接続されている各コンポーネントについて、BFSを使用して、それが二倍であるかどうかを判断します。 それが二倍でない場合、-1。を返します

     • グループカウントを計算します：
  接続された各コンポーネントの場合、BFSを使用して最大深度を決定し、グループの最大数を表します。

  3. 結果を組み合わせます：
     すべての二部コンポーネントの最大グループカウントを合計します。

  4. 計画
     隣接リストとしてグラフを構築します。
  接続されたコンポーネントをグループ化するために組合ファインドを使用します グラフ内の各ノードの

  ： BFSを使用して、グラフが二部であるかどうかを確認し、そのコンポーネントの最大深度を計算します。

  1. 結果として、すべてのコンポーネントの深さの合計を返します。いずれかのコンポーネントが二部でない場合は、-1を返します
  2. このソリューションをPHP：
  2493に実装しましょう。ノードをグループの最大数に分割します

  3. • <?php /**
        * @param Integer $n
        * @param Integer[][] $edges
        * @return Integer
        */
       function magnificentSets($n, $edges) {
           ...
           ...
           ...
           /**
            * go to ./solution.php
            */
       }
       
       /**
        * @param $graph
        * @param $u
        * @return int
        */
       private function bfs($graph, $u) {
           ...
           ...
           ...
           /**
            * go to ./solution.php
            */
       }
       
       class UnionFind {
           /**
            * @var array
            */
           private $id;
           /**
            * @var array
            */
           private $rank;
       
           /**
            * @param $n
            */
           public function __construct($n) {
              ...
              ...
              ...
              /**
               * go to ./solution.php
               */
           }
       
           /**
            * @param $u
            * @param $v
            * @return void
            */
           public function unionByRank($u, $v) {
              ...
              ...
              ...
              /**
               * go to ./solution.php
               */
           }
       
           /**
            * @param $u
            * @return mixed
            */
           public function find($u) {
              ...
              ...
              ...
              /**
               * go to ./solution.php
               */
           }
       }
       
       
       // Example usage:
       $n = 6;
       $edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
       echo maxGroups($n, $edges); // Output: 4
       
       $n = 3;
       $edges = [[1,2], [2,3], [3,1]];
       echo maxGroups($n, $edges); // Output: -1
       ?>
       

       説明：

       1。ユニオンファインドクラス

       ユニオンファインド（Disjoint Set Union）構造グループノードを接続されたコンポーネントにグループ化し、2つの主要なタスクを実行します。

       • find：ノードの接続されたコンポーネントのルートを識別します。
       • ユニオン：ランクに基づいて2つの接続されたコンポーネントをマージします
       2。二部チェックと深度計算のためのBFS
       bipartite検証：
       • BFSを使用して、ノードに「色」を交互に割り当てます。隣接するノードが同じ色を共有している場合、グラフは二部ではありません。
       深さ計算：
       • BFSツリーの深さを測定して、グループの最大数を決定します。
       3。結果を結合します

       接続された各コンポーネントの最大深度を計算します。

       すべてのコンポーネントの深さを追加して、結果を決定します。
       • 例のウォークスルー

       例1

       入力：

       手順：
       

       $n = 6;  
       $edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
       

       隣接するコンストラクトリスト：
       接続されたコンポーネントでBFSを使用します。

          1 -> [2, 4, 5]
          2 -> [1, 3, 6]
          3 -> [2]
          4 -> [1, 6]
          5 -> [1]
          6 -> [2, 4]
       

       コンポーネント1：Bipartite。最大深さ=4。
       1. すべてのコンポーネントにわたる
          • 和の深さ：4。
       出力：4
       例2

       入力：

       手順：
       

       $n = 3;  
       $edges = [[1,2], [2,3], [3,1]];
       

       隣接するコンストラクトリスト：
       bfsを使用してください：

          1 -> [2, 3]
          2 -> [1, 3]
          3 -> [1, 2]
       

       コンポーネント1：bipartiteではありません。
       1. output：-1
       時間の複雑さ

       グラフの構築：

       • o（e）、ここで、e はエッジの数です。 union-find：
       o（α（n））
       • 、ここで bfs：o（v e）、ここで、
       v
       • は頂点の数です。 全体的な複雑さ：o（n e） 例のための出力 このアプローチは、組合員を使用してコンポーネント管理を簡素化しながら、二極性チェックと深度計算のためにBFSを活用することにより、グループ化の問題を効率的に処理します。ソリューションは、接続されたグラフと切断されたグラフの両方を処理します 連絡先リンク
       このシリーズが役立つと思った場合は、

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

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

       $n = 6;
       $edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
       echo magnificentSets($n, $edges); // Output: 4
       
       $n = 3;
       $edges = [[1,2], [2,3], [3,1]];
       echo magnificentSets($n, $edges); // Output: -1
       

       linkedIn

       github

以上がノードをグループの最大数に分けますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。