国家集训队作业sgu413解题报告

1、SGU413 Berland Divi解题问题简述：给出一个顶点数为偶数的连通图，将其分成若干不相交的子图，使得每个子图都是一棵顶点数大于 1 的树。(题目没对无解时如何输出做出解释)问题分析：本题要将一个图分解，那么如何分解?如何保证一个子图是一棵树呢？这都是非常麻烦的事情。另外图的顶点是偶数，这个条件有什么用呢？如果顶点数为奇数，显然一个长度为 3 的环就是无解的，那么偶数是否就意味着一定有解呢？让一步步分析。直接把图分解是比较的，可以尝试利用图的生成树的某些性质，找出图上已有的树。比较容易想到的当然就是简单的 DFS 生成树了。那么DFS 生成树有什么性质呢?不难发现生成树上的任意节点和

2、其儿子组成的子图在原图中肯定是一棵树。因为儿子之间是不会有边相连的，否则由 DFS 的性质，他们不可能成为兄弟。这样不难得出一个贪心的算法，利用把任意节点和其儿子的子图在原图中都是一棵树的性质，可以从 DFS 树的叶子开始往上分组，把当前节点和未分组的儿子分为同一组。如果不存在未分组的儿子则当前节点标记为未分组。下图是一个例子：相同颜色的分为一组显然这个算法存在一个缺陷，就是根节点可能没有分进任何一组。如下图左边所示：这该如何解决呢？实际上该算法成功与否与DFS 生成树的形态有很大关系。对于上图的情况，如果把原来根红色的儿子作为新根就能得到右图的可行可以采用枚举根甚至随机改变 DFS 顺序的方

3、法来多次求解。而对解。因此于SGU 的数据，只需要枚举根就可以Accept 了。这个算法十分简洁，而且正确率极高，时间复杂度为 O(NM)。但这样的算法并不完美，而且没有利用到 N 为偶数的性质，分析。还需进一步算法改进：上文算法只在根节点处会出现问题，就从这下手。首先还是按照上文的算法遍历图，如果根节点已经在某组内则已得到可行解，否则先尝试把根添加到某一组内，如果根只与该组中的一个点相连则直接添加，同样得到一组可行解。而如果无法添加，为得到可行解势必要改变原有的分组方式。并且要注意到此时任一组与根之间至少有两条边。让先来根节点儿子所在的组。如果该组只有两个点，则此时根必然与这两个点形成一个长

4、度为 3 的环，无法通过调整得到可行解。而如果该组不止两个节点，由于每一组都是一个父亲带上若干个儿子的形式，必然存在某个儿子与根有边相连，这样把它和根分成一组，其他分组方式不变就可行解。下图是一个例子：实线为 DFS 树边，虚线为原图的非树边。那么当所有根的儿子所在的组都只有两个点时，又该怎么办呢?这时就要利用 N 为偶数的条件了。显然根以及根的儿子所在的组的所有节点的总数为奇数，那么剩下的节点个数也为奇数。即下图所有绿色三角形(每个三角形为一棵去掉根的)中的点的个数为奇数。由奇偶分析知，必然有一个的三角形节点数为的奇数(下图中用深绿色表示)，加上其的根便总共有偶数个节点，而且这棵是连通的。这样不就和原问题的条件相同了吗?因此可以把这部分递归求解，而把多余的那个节点和根分为同一组，其他不变即可。按照上文的算法，每次要么小的子问题，所以到最后已经得到可行解，要么得到一个规模减会得出正确解。而且递归最多进行 N/2 次