题解：CF1792F1 Graph Coloring (easy version)

红蓝互为补图，因此红蓝都不连通的情况不存在。

第一反应是对红蓝都连通的情况容斥，但是发现这样根本做不了。

不妨转化为有一个颜色不连通，对恰有一种颜色不连通的情况计数，此时另一种颜色必定连通。

令 $f_i$ 表示 $i$ 个点，每个子集满足蓝色不连通的方案数，枚举与 $1$ 相连极大的蓝色连通块 $S$，保证跨过 $S$ 和 $[1,i]/S$ 的集合中不存在红蓝都连通的集合，这个连通块需要满足红色不连通，用“极大”保证不重。

由于是"极大连通块"，所以两个集合之间的连边方案是固定的，只能是红色边。

恰好，这样的连边方式满足【跨过 $S$ 和 $[1,i]/S$ 的集合中不存在红蓝都连通的集合】，因此逻辑以一种很奇怪的方式自洽了。

由于对称性，红色不连通方案数 $=$ 蓝色不连通方案数。

则 $f_i=\sum\limits_{j=1}^{n-1}\binom{i-1}{j-1}\times f_{j}\times (2f_{n-j}-[n-j=1])$。

乘二是因为当集合有边时可以任意交换红蓝。