P9625 [ICPC2020 Nanjing R] Degree of Spanning Tree 题解

WhitD · 2023-09-12 11:18:55 · 题解

题目大意

给定一个具有 n 个顶点和 m 条边的无向图，找到一个图的生成树，使得生成树中的每个顶点的度数不大于 \frac{n}{2}。

思路

对于有 n 个点的生成树，其边数为 n-1，总度数为 2n-2，因此至多只有一个点的度数会大于 \frac{n}{2}。

我们可以先把这个图的任意一个生成树找出来，然后找到这个生成树中度数大于 \frac{n}{2} 的点（要是找不到说明这个生成树已经满足条件了，直接输出就可以），将这个点设为生成树的根节点，枚举所有不在生成树上的边，先将这条边加进去，然后判断图中是否形成了包含根节点的环……

如图：蓝色边是初始生成树，红色点是根节点，黄色边是当前枚举到的边，不难看出图中的绿色边形成了一个包含根节点的环。

此时我们需要删除一条绿色边才能保证还是生成树，请注意我们的目的是为了减小根节点的度数，因此一定是优先删除与根节点相连的边，会有如下两种情况：

注意第二种情况，虽然根节点的度数小于 \frac{n}{2} 了，但是橘色点的度数又大于 \frac{n}{2} 了。我们发现原生成树中橘色点的度数为 2，而右下角的点度数为 1，也就是说我们在删边时需要优先删除度数大的点与根节点所连的边。

综上，我们得到了在删边时需要遵守的规则：优先删除与根节点相连的边，并且是度数大的节点与根节点相连的那条边（注意特判无解情况）。