ノードをグループの最大数に分けます-PHPチュートリアル-php.cn

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

難易度：hard

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

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

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

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

1インダックス

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

i
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：
- 入力：

output：

-1

説明：

グループ化が不可能であることが示される可能性があります。
4 edges [i] .length == 2

1＆lt; = a i、B a

！= b
頂点の任意のペアの間に最大1つのエッジがあります。
ヒント：
1. グラフが二部でない場合、ノードをグループ化することはできません。
2. 最後に、接続された各コンポーネントの問題を解決するために、ノードVの場合、その位置を左端グループに修正すると、他のすべてのノードの位置を評価できることがわかります。その位置は、ノードv。
解決策：
問題、
「ノードをグループの最大数に分割する」
には、対応のないグラフのノードを分割できるグループの最大数を決定することを伴います。各ノードは、正確に1つのグループに属します。
2. キーポイント
グラフのプロパティ：
グラフが切断される場合があります。
- 検証：接続されたコンポーネントごとに、Bipartiteであるかどうかを確認します。そうでない場合は、-1。
- 二倍性の性質：ソリューションにはBFSが含まれ、二極性を検証します
- 統合ファインド：接続されたコンポーネントを効率的にグループ化するのに役立ちます。
- アプローチ
前処理：
1. 隣接リストを使用してグラフを表します。組合ファインドを使用して、接続されたコンポーネントを識別します。
  - bfs bipartitenessを検証する：
2. 接続されている各コンポーネントについて、BFSを使用して、それが二倍であるかどうかを判断します。 それが二倍でない場合、-1。を返します
  - グループカウントを計算します：
3. 結果を組み合わせます：
  すべての二部コンポーネントの最大グループカウントを合計します。
4. 計画
  隣接リストとしてグラフを構築します。
接続されたコンポーネントをグループ化するために組合ファインドを使用しますグラフ内の各ノードの
： BFSを使用して、グラフが二部であるかどうかを確認し、そのコンポーネントの最大深度を計算します。
1. 結果として、すべてのコンポーネントの深さの合計を返します。いずれかのコンポーネントが二部でない場合は、-1を返します
2. このソリューションをPHP：
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
  - BFSを使用して、ノードに「色」を交互に割り当てます。隣接するノードが同じ色を共有している場合、グラフは二部ではありません。
  - BFSツリーの深さを測定して、グループの最大数を決定します。
  接続された各コンポーネントの最大深度を計算します。
  - 例のウォークスルー
  例1
  
  入力：
  
  手順：
```
  $n = 6;  
  $edges = [[1,2], [1,4], [1,5], [2,6], [2,3], [4,6]];
```
  ログイン後にコピー
  隣接するコンストラクトリスト：
```
     1 -> [2, 4, 5]
     2 -> [1, 3, 6]
     3 -> [2]
     4 -> [1, 6]
     5 -> [1]
     6 -> [2, 4]
```
  ログイン後にコピー
  コンポーネント1：Bipartite。最大深さ=4。
  1. - 和の深さ：4。
  例2
  
  入力：
  
  手順：
```
  $n = 3;  
  $edges = [[1,2], [2,3], [3,1]];
```
  ログイン後にコピー
  隣接するコンストラクトリスト：
```
     1 -> [2, 3]
     2 -> [1, 3]
     3 -> [1, 2]
```
  ログイン後にコピー
  コンポーネント1：bipartiteではありません。
  時間の複雑さ
  
  グラフの構築：
  - o（e）、ここで、e はエッジの数です。 union-find：
  - 、ここで bfs：o（v e）、ここで、
  - は頂点の数です。全体的な複雑さ：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