将节点分为最大组数

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中文网其他相关文章！