题目传送门 引 属于一眼题,不看时间限制 8 s 8s 8s 容易被诈骗 解法 简单容斥 大概 式子就是 ∑ ( − 1 ) M ∗ K ∣ S ∣ \sum(-1)^{M}*K^{|S|} ∑(−1)M∗K∣S∣ , M M M 为边集的大小， ∣ S ∣ |S| ∣S∣ 为联通块的数量 那么我们就有 空间复杂度： O ( 2 N ) = 1 e 9 O(2^N) =1e9