[Poi2011]Conspiracy

给定一张图 (G)，将其划分成两个集合 (S) 和 (T)，满足 (Sland T=varnothing,Slor T=G,S e varnothing,T e varnothing)。

其中 (S) 为一个团，(T) 为一个独立集。求方案数。

(nle 5000)

( m Sol:)

做一点观察，如果我们有一组合法解，接下来需要调整。

我们发现独立集中的任意两个点不能被一起选入团，团中任意两个点不能被选入独立集。

于是假设得到了一组合法解，那么我们只能枚举将团中一个点选入独立集，然后将独立集中至多一个点调整入团。

求解合法解通过 ( m 2-sat) 实现，假设 (i) 被选入团，那么与 (i) 没有边的点必须在独立集中，假设 (i) 被选入独立集，那么与 (i) 有边的点必须在团中。

通过 ( m 2-sat) 求得一组合法解之后，我们先枚举只调整一个点的情况，然后对于两个点的情况，独立集中的这个点要与团中其他点均有边，预处理一下节点，分别特判即可，复杂度 (mathcal O(n^2))