首页 > 其他分享 >CF986C AND Graph(图论+二进制连边)

CF986C AND Graph(图论+二进制连边)

时间:2022-08-14 17:58:15浏览次数:91  
标签:连边 int Graph CF986C vis Maxm

CF986C AND Graph

\(\color{yellow}{\bigstar\texttt{Hint}}\):和每个点连接的点是这个数取反后的子集,考虑将这个点和它的反连边,那么所有对应的数的子集都是同一个连通块内的。

之后的一种简单的寻找连通块就是直接对所有没有访问过的点暴力访问标记即可。

#define Maxn 23
#define Maxm 5000005
int n,m,All,ans;
int a[Maxm];
bool vis[Maxm],exi[Maxm];
void dfs(int x)
{
	vis[x]=true;
	for(int i=0;i<n;i++) if(((x>>i) & 1) && (!vis[x^(1<<i)])) dfs(x^(1<<i));
	if(exi[x] && !vis[All^x]) dfs(All^x);
}
int main()
{
	n=rd(),m=rd(),All=(1<<n)-1;
	for(int i=1;i<=m;i++) a[i]=rd(),exi[a[i]]=true;
	for(int i=1;i<=m;i++) if(!vis[a[i]]) ans++,vis[a[i]]=true,dfs(All^a[i]);
	printf("%d\n",ans);
	return 0;
}

标签:连边,int,Graph,CF986C,vis,Maxm
From: https://www.cnblogs.com/EricQian/p/16585890.html

相关文章

  • [WATER]玩了一下 Graph Editor
    GraphEditor稳定的六边形无论多么扭曲,边长设小后基本总会猛烈跳动后保持平衡。123456789101112131415161718192021222324252627282930......