P11054

挺有趣的思维题。

• sub 1,2

对于每一个点枚举颜色，考虑吧这个点之外所有的点都染成一个颜色，若是只有以个连通块就代表当前点就是这个颜色，构造数 $n^2$。

• sub 4

完全图，所有的相同颜色的点都在一个连通块，这样可以判断出一个子图的连通块数量，可以对于每个的点进行二分颜色即可。

• sub 3

原图是一条链的情况，根据之前的方法我们可以想到：如果一个未知的点的相邻点中存在与他颜色相同的点，连通块数量就会减少。考虑对于链的奇偶性分成两部分，对于每部分枚举颜色，对于一种颜色我们每次寻找到当前第一个为这种颜色的点，每次只需二分就可做到 $2n + n \log n$。

• sub 5

根据之前的观察，我们需要知道所有连通块的情况，这样方便我们统计子图的联通快数量。

对于当前一个图进行加点，每次加入一个点之后，对于与他相邻并且已经出现在子图内的点进行和并，由于一个点可能需要与很多点进行合并，所以按照之前的方法，每次进行枚举第一个点二分，次数是 $n + \log n$。

考虑我们已经知道了连通块的情况，现在要记录颜色。按照之前的方法，我们要分成两部分，而且要保证每部分不存在一个点所有相邻的点都是与他一部分的，直接进行黑白染色即可，接下来和之前一样。

由于我们在染色时只需要保留一个连通块中的一个点即可，所以理论次数是 $3n + \log n$ 。

时间复杂度 $O(n^3 \ log n)$。