图论做题记录

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：从最大度数的点下手，和它不连通的导出子图大小会被降下来。