Readme

2493.Divide-Nodes-Into-the-Maximum-Number-of-Groups

本题的突破点是，只要我们能确定一个节点作为第一个group，那么剩下的节点该如何安排其实是可以贪心地确定的：很显然只要用BFS进行层级遍历即可，就像生成一棵树一样，把同属于一个层级的放入一个group，不停往下扩展，这样就可以得到最多的层级（也就是group）。

因为本题要求同一个group不能有边，所以我们需要检查一下这种方法得到的拓扑结构：是否有任何点指向了同一层级的其他点。有的话就标记BFS。特别注意的是，如果发现了这种情况，不仅意味着从当前根节点出发的BFS无解，也意味着整个连通图无解，即你从此连通图的任何一个位置作为根，都无法得到合法的层级结构。

因此，遍历起点的循环是V次，每次BFS需要至多访问E条边。总的时间复杂度是o(VE)恰好符合要求。

有人会问，以上的方法约定了第一个group只能有一个节点（看做是根）。可不可能有两个节点A与B都是处于第一个group的最优解呢？答案是不会更优。当A与B（第一层级）都和C（第二层级）联通时，我们其实按照之前的方法，会把B看做是第三个层级，显然这个方案能够得到更多的group。

此外，本题可能会有多个不同的联通区域。最终答案是每个联通区域所能构造出的最大group数量之和。一种处理方法是先用Union Find把不同联通区域的节点都标记出来，接着再遍历每个联通区域，变换根的位置去做BFS的尝试。另一种处理方法可以直接遍历每个节点作为根，BFS完之后记得将遇到的最小编号的节点作为联通区域的代号，最后我们将不同联通区域的答案再相加。