[学习笔记] 二分图判定

定义

先看一下什么是二分图:

[学习笔记] 二分图判定

可以发现,这个图被分成了两个集合,每个集合之间的点都没有边相连,每条边都是在两个集合的点之间

判定

知道了定义后我们需要知道如何去判定一个图,它是不是二分图

我们一般会使用染色法

首先我们需要知道二分图的一个性质:

二分图不存在长度为奇数的环

因为每条边都是从一个集合到另一个集合,如果要回到一个集合那只能走偶数次

这种方法是把所有的点分成两种颜色(对应两种集合),如果这张图是二分图,那么每条边连接的两个点的颜色

都应该是不同的

所以我们从第一个点开始,把它染成\(1\),然后把和它相连的边染成\(-1\)

如果我们要染色的点已经有了颜色并且和当前点的颜色是相同的,那么这就不是二分图

code
 for(int i=1;i<=n;i++)
	if(!c[i])
	    if(!dfs(i,1))
		  cout<<"NO"<<endl;
bool dfs(int u,int col){
    c[u]=col;
    for(int i=head[u];i;i=nxt[i]){
	int v=ver[i];
	if(!c[v]&&!dfs(v,-col)) return 0;
	else if(c[v]==col) return 0;
    }
    return 1;
}

至于为什么每个点都要dfs一下,因为二分图可能不是连通的,以下为同一个图:

[学习笔记] 二分图判定

[学习笔记] 二分图判定

\(Q\):每个点开始dfs的时候都染成\(1\),万一开始染色点是和点\(1\)在不同集合怎么办?

可以手动模拟下一上图,其实每次dfs都会把连通的一整部分搜完,当然也不可能搜到之前的点啦

其实染色法判断的就是:同一集合有没有边相连

上一篇:算法从入门到放弃——第六期 岛屿(II)


下一篇:三子棋游戏