开发笔记:Codeforces986CANDGraphdfs

原文链接https://www.cnblogs.com/zhouzhendong/p/9161514.html

　　给定 $n,m (0leq nleq 22,1leq mleq 2^n)$ 。

　　接下来给定 $m$ 个数，记第 $i$ 个数为 $a_i$ ，对于所有 $a_i$ ，满足 $0leq a_ileq 2^n$ 。

　　第 $i$ 个数与第 $j$ 个数有无向边，当且仅当 $a_i AND a_j=0$ 。其中 $"AND"$ 是按位与。

　　问在以这 $m$ 个数为节点的无向图中有多少个各自独立的连通块。

　　考虑有有连边的条件。

　　我们记 $"AND"$ 为按位与运算， $"OR"$ 为按位或运算， $"XOR"$ 为按位异或运算。

　　我们记 $s=2^n-1$ 。

　　如果 $a$ 与 $b$ 有连边，那么满足 $b in {x| x OR (s XOR a) = (s XOR a) }$。

　　于是我们考虑记忆化dfs。

　　我们用 $v[y]$ 表示集合 ${x|x OR y=y}$ 是否被访问过。

　　在 dfs 的过程中，dfs 一个 $y$ ，我们就要访问其所有子集。

　　如果当前的 $y$ 在 $a$ 数组中出现过，那么我们确定了上一个数与当前数的连通关系，而且我们要继续 dfs，在 $ s XOR y $ 代表的集合中 dfs 查找是否有新的数字连通。

　　由于连通性具有传递性和对称性，所以每次dfs可以排除一块连通块。

　　然后就简单统计一下就可以了。