DeepSeek LeetCode 2493. 将节点分成尽可能多的组 public int magnificentSets(int n, int[][] edges)

这道题是2493. 将节点分成尽可能多的组本质上是一个图论 BFS 分层 连通分量处理的问题。题意理解我们需要将图中的节点分成若干组使得每条边连接的两个节点必须属于相邻的组组号差为 1组号从 1 开始连续编号求最大可能的组数如果不可能则返回 -1等价于找到一种给节点标号的方式使得相邻节点标号差 1且标号从 1 开始连续最大化最大标号。核心思路重要观察每个连通分量独立处理如果图不是二分图直接返回 -1因为相邻节点标号差 1 意味着图必须是二分图对每个连通分量尝试以每个节点作为起点用 BFS 计算最大深度即该起点下的最大组数连通分量的最大组数 该分量中所有起点计算得到的最大深度最终答案 所有连通分量的最大组数之和实现步骤建图检查每个连通分量是否为二分图BFS 染色对每个连通分量对每个节点尝试作为起点BFS 分层求最大深度取各连通分量的最大值之和代码实现importjava.util.*;publicclassSolution{publicintmagnificentSets(intn,int[][]edges){// 建图ListInteger[]graphnewArrayList[n];for(inti0;in;i){graph[i]newArrayList();}for(int[]edge:edges){intuedge[0]-1;intvedge[1]-1;graph[u].add(v);graph[v].add(u);}// 染色数组用于二分图检测和连通分量划分int[]colornewint[n];Arrays.fill(color,-1);ListListIntegercomponentsnewArrayList();// 第一步染色并划分连通分量for(inti0;in;i){if(color[i]!-1)continue;ListIntegercomponentnewArrayList();QueueIntegerqueuenewLinkedList();queue.offer(i);color[i]0;component.add(i);booleanisBipartitetrue;while(!queue.isEmpty()){intuqueue.poll();for(intv:graph[u]){if(color[v]-1){color[v]color[u]^1;queue.offer(v);component.add(v);}elseif(color[v]color[u]){isBipartitefalse;}}}if(!isBipartite){return-1;// 不是二分图无法完成分组}components.add(component);}// 第二步对每个连通分量计算最大深度inttotalGroups0;for(ListIntegercomponent:components){intmaxDepth0;// 尝试以每个节点作为起点for(intstart:component){intdepthbfsMaxDepth(graph,start,component.size());maxDepthMath.max(maxDepth,depth);}totalGroupsmaxDepth;}returntotalGroups;}// BFS 求以 start 为起点的最大深度privateintbfsMaxDepth(ListInteger[]graph,intstart,intn){int[]distnewint[graph.length];Arrays.fill(dist,-1);QueueIntegerqueuenewLinkedList();queue.offer(start);dist[start]1;// 起始组号为 1intmaxDepth1;while(!queue.isEmpty()){intuqueue.poll();for(intv:graph[u]){if(dist[v]-1){dist[v]dist[u]1;maxDepthMath.max(maxDepth,dist[v]);queue.offer(v);}elseif(Math.abs(dist[v]-dist[u])!1){// 如果相邻节点的距离差不是 1说明这种分组方式不可能// 但根据二分图性质这里其实不会发生为了保险可以返回 -1// 实际因为已经验证是二分图且 BFS 分层自然满足条件}}}returnmaxDepth;}}更优化的版本直接 BFS 计算最大深度classSolution{publicintmagnificentSets(intn,int[][]edges){ListInteger[]gnewArrayList[n];for(inti0;in;i){g[i]newArrayList();}for(int[]e:edges){intae[0]-1,be[1]-1;g[a].add(b);g[b].add(a);}int[]colornewint[n];Arrays.fill(color,-1);ListListIntegercompsnewArrayList();// 二分图检测和连通分量划分for(inti0;in;i){if(color[i]!-1)continue;ListIntegercompnewArrayList();QueueIntegerqnewLinkedList();q.offer(i);color[i]0;comp.add(i);booleanoktrue;while(!q.isEmpty()){intuq.poll();for(intv:g[u]){if(color[v]-1){color[v]color[u]^1;q.offer(v);comp.add(v);}elseif(color[v]color[u]){okfalse;}}}if(!ok)return-1;comps.add(comp);}intans0;for(ListIntegercomp:comps){intmaxDepth0;// 对连通分量中每个点尝试作为起点for(intstart:comp){int[]distnewint[n];Arrays.fill(dist,-1);QueueIntegerqnewLinkedList();q.offer(start);dist[start]1;intdepth1;while(!q.isEmpty()){intuq.poll();for(intv:g[u]){if(dist[v]-1){dist[v]dist[u]1;depthMath.max(depth,dist[v]);q.offer(v);}}}maxDepthMath.max(maxDepth,depth);}ansmaxDepth;}returnans;}}复杂度分析时间复杂度O(n × (n m))最坏情况每个连通分量 O(n) 个起点每个 BFS O(n m)空间复杂度O(n m)关键点总结二分图判断相邻节点标号差 1 意味着图必须是二分图BFS 分层每个 BFS 能求出以某点为起点的最大组数连通分量独立不同连通分量的组号可以独立编号取最大值对每个连通分量取所有起点 BFS 结果的最大值这道题的核心是发现问题转化为二分图 BFS 求最长链并且理解不同连通分量之间可以重新从 1 开始编号。