图论做题记录

CF242D

题意：初始有一个 (n) 个点的图，依次添加 (m) 条边，对每次加边后需要回答满足每个点的度数都大于等于 (k) 的导出子图的最大点数。

考虑将加边操作改为删边操作，关键问题在于怎么求出最后状态的答案。考虑每一个初始点数小于 (k) 的点一定不能被加入答案，直接将其删除，在观察删除它之后会使那些点不合法，在重复当前操作，最后剩下的点都是合法的点。对于每次删边操作，即考虑删除这条边后会不会使两点的度数小于 (k)。复杂度线性。

Trick：用类似拓扑排序的方法每次删去不合法点的方法。还有几道类似的例题：CF242D。

CF920E

题意：初始有一个 (n) 个点的无向完全图，删去其中 (m) 条边，求有多少个连通分量以及每个连通分量的点数。

考虑鸽巢原理，必定有一个点剩余的度数大于等于 (n - frac{m}{n} - 1)。考虑将与这个点相连的点全部合并起来，那么只会剩下 (frac{m}{n}) 个点未被连通。暴力处理这 (frac{m}{n}) 个点的复杂度为 (O(n cdot frac{m}{n}))。所以总时间复杂度为 (O(n + m))。

Trick：从最大度数的点下手，和它不连通的导出子图大小会被降下来。