検索

ホームページ >バックエンド開発 >PHPチュートリアル >ノードをグループの最大数に分けます

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

Linda Hamilton
Linda Hamiltonオリジナル
2025-01-30 10:03:10561ブラウズ

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. 接続された各コンポーネントの問題を個別に解決できることに注意してください。最終的な答えは、各コンポーネントのグループの最大数の合計にすぎないことに注意してください。
    2. 最後に、接続された各コンポーネントの問題を解決するために、ノードVの場合、その位置を左端グループに修正すると、他のすべてのノードの位置を評価できることがわかります。その位置は、ノードv。
      3. でルート化した後のBFSツリーのノードの深さです。
    解決策：

    問題、

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

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

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

    グラフのプロパティ：

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

    前処理：

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

      • bfs bipartitenessを検証する：

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

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

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

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

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

    1. 結果として、すべてのコンポーネントの深さの合計を返します。いずれかのコンポーネントが二部でない場合は、-1を返します
    2. このソリューションをPHP：
      3. 2493に実装しましょう。ノードをグループの最大数に分割します
      • <?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]];
        隣接するコンストラクトリスト：

          2. 接続されたコンポーネントでBFSを使用します。 
           1 -> [2, 4, 5]
   2 -> [1, 3, 6]
   3 -> [2]
   4 -> [1, 6]
   5 -> [1]
   6 -> [2, 4]
        コンポーネント1：Bipartite。最大深さ=4。
          1. すべてのコンポーネントにわたる
          • 和の深さ：4。
          2. 出力：4
        例2

        入力：

        手順：

        $n = 3;  
$edges = [[1,2], [2,3], [3,1]];
        隣接するコンストラクトリスト：

          2. bfsを使用してください： 
           1 -> [2, 3]
   2 -> [1, 3]
   3 -> [1, 2]
        コンポーネント1：bipartiteではありません。
            • 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 サイトの他の関連記事を参照してください。

php edge Integer Array if count for while union using class Length finally number function this position input github Other
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
前の記事：。冗長接続次の記事：。冗長接続

関連記事

続きを見る