Luogu3513 [POI2011] KON-Conspiracy

题意：给出一张 个点的无向图，求将点集划分为一个独立集和一个团（均非空）的方案数。

，时限 。

---

单独求解独立集或团是非常困难的，要利用它们本身的强性质来简化问题。

考虑若已经得到一组方案 （其中前者是独立集后者是团）。

若从 中移动两个（及以上）点至 ，则这两个点之间必然没有边，不合法。

若从 中移动两个（及以上）点至 ，则这两个点之间必然有边，不合法。

综上，所有其他合法方案必然是 改动一个点产生的。（注意可能同时移动）

因此，我们先来考虑如何构造出一组合法方案。

建立 模型， 表示点 在独立集内， 表示点 在团内。

表示 为真能推导出 为真，则有如下连边 ：

• 若图中 不相连：

• 若图中 相连：

缩点后拓扑排序即可构造出任意一组解。

接着，枚举改动并暴力判定是否合法即可统计答案。

复杂度为 。

---

然而这个做法还是太丑了……谁说转化后的模型就一定更简单呢？

考虑若已经得到一组方案 （其中前者是独立集后者是团），且使得 尽量大。

那么， 中的点度数至少为 ，而 中的点度数至多为 （若 则不是独立集，若为 则可以加入团），故团一定是由度数较大的若干个点组成的。

进一步地，若总边数为 ，则团内部边数为 ，这是充要条件。

于是，将点度从大到小排序后，判定每个前缀是否可行，即可构造方案。

假设我们选择的度数最小的点度数为 ，选了 个，但实际上有 个，则可以更换，方案数为 。