將節點分為最大組數

2493。將節點分為最大組

>

難度： hard

>主題：廣度優先搜索，聯合查找，圖形

>給您一個正整數n，代表無向圖中的節點的數量。節點從1到n。 >您還會給您一個2D整數數組邊緣，其中邊緣[i] = [a

i

，b_i>]表示存在_{bivecrectional} 節點ai 和b_i之間的邊緣。 _通知可以斷開給定的圖。 > 將圖的節點劃分為M組（

1個索引

），這樣的節點是：>

圖中的每個節點完全屬於一個組。

>
• 對於圖中的每個節點，由邊緣連接的[a
i
• ，b _i]使用索引X，B_i屬於索引y的組，然後| y -x | = 1. _返回>您可以將節點劃分的最大組數（即最大值）。返回
-1如果不可能將節點與給定條件

。

分組 >>示例1：

>輸入： n = 6，edges = [[1,2]，[1,4]，[1,5]，[2,6]，[2,3]，[4,6 ] ]

>輸出：

4
• >說明：
>如圖所示：
• >將節點5添加到第一個組。
>將節點1添加到第二組。
• >將節點2和4添加到第三組。
  >將節點3和6添加到第四組。
  • >
  我們可以看到每個邊緣都可以滿足。
  >可以證明，如果我們創建第五組並將任何節點從第三或第四組移動到其中，那麼至少在邊緣上都無法滿足。
  • >
  • >
  >示例2：
>輸入：

n = 3，edges = [[1,2]，[2,3]，[3,1]]

>輸出：

-1

• >說明：如果將節點1添加到第一個組，將節點2添加到第二組中，然後將節點3添加到第三組以滿足前兩個邊緣，我們可以看到，第三個邊緣將不滿足第三個邊緣。
• 可以證明不可能分組。
• >約束：
  • >
  1＆lt; = n＆lt; = 500 >
1＆lt; = edges.length＆lt; = 10 4
edges [i] .length == 2
• 1＆lt; = a
i
• ，bⁱ＆lt; = n
• a
i
• ！ = b_i> 在任何一對頂點之間最多都有一個邊緣。
>
• 提示：
  1. 如果圖不是雙分，則不可能分組節點。 >請注意，我們可以獨立解決每個連接的組件的問題，最終答案將只是每個組件中最大組的總數。 >
  >最後，要解決每個連接的組件的問題，我們可以注意到，如果對於某個節點V，我們將其位置固定在最左邊的組中，那麼我們也可以評估其他每個節點的位置。該位置是紮根在節點v。
  解決方案：

  問題，

  “將節點分為最大組數”

  ，涉及確定可以將無向圖的節點劃分的最大組數，以：

  每個節點恰好屬於一個組。 相鄰節點的
  組成的索引恰好有1個。 如果該圖不是雙分部分，則不可能進行分組，並且該函數必須返回-1。
  2. >關鍵點

  圖形屬性：

  該圖可以斷開連接。
  >
  • >驗證：對於每個連接的組件，檢查它是否是雙分。如果沒有，返回-1。
  • >二分性質：解決方案涉及BFS以驗證雙方。
  • 聯合 - 芬德：有效地分組連接的組件。 >
  • 方法

  預處理：

  1. 使用鄰接列表表示圖形。 >使用Union-Find來識別連接的組件。

     • bfs驗證兩肢：
     >
  2. 對於每個連接的組件，請使用BFS確定它是否為雙分。

     如果不是雙分，請返回-1。

     • >計算組計數：
     對於每個連接的組件，使用BFS確定最大深度，代表組的最大數量。

  3. 組合結果：

     • 概括所有兩部分組件的最大組計數。
     >

  4. 計劃

     • 構建圖形作為鄰接列表。
     >使用Union-Find對組連接的組件。
  圖中每個節點的
  >：

  >使用BFS檢查圖形是否是雙分部分，併計算該組件的最大深度。

  1. >作為結果，返回所有組件深度的總和。如果任何組件不是雙方，請返回-1。
  >讓我們在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。 Union-Find類

       > Union-Find（不連接集合聯合）結構將節點組為連接的組件，並執行兩個主要任務：

       • find：>標識節點連接的組件的根。
       • 聯合：>根據等級合併兩個連接的組件。

       2。 BFS用於兩分和深度計算

       • >二分化驗證：使用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：兩分。最大深度= 4
       1. 所有組件中的總和深度：4。
          >輸出：4
       2. >示例2

       輸入：

       步驟：

       
       >構造鄰接列表：

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

       使用BFS：
       組件1：不是雙方。

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

       1. >輸出：-1
          時間複雜度

       圖形結構：

       o（e）
       • ，其中e 是邊緣的數量。 > >聯合- find：
       • o（α（n）） ，其中n 是節點的數量（由於路徑壓縮而幾乎恆定）。
       • bfs：o（v e） ，其中 v 是頂點的數量。 總體複雜性：o（n e）
       >
       >輸出示例

       $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
       

       這種方法通過利用BFS進行兩性檢查和深度計算來有效地處理分組問題，同時利用Union-Find來簡化組件管理。該解決方案處理連接和斷開的圖形。

       聯繫鏈接

       如果您發現此系列有幫助，請考慮在Github上給出 reposority >在您喜歡的社交網絡上分享帖子？您的支持對我來說意義重大！

       >

       如果您想要這樣的更多有用的內容，請隨時關注我：
       >
       • LinkedIn
       • github

以上是將節點分為最大組數的詳細內容。更多資訊請關注PHP中文網其他相關文章！