定义
先看一下什么是二分图:
可以发现,这个图被分成了两个集合,每个集合之间的点都没有边相连,每条边都是在两个集合的点之间
判定
知道了定义后我们需要知道如何去判定一个图,它是不是二分图
我们一般会使用染色法
首先我们需要知道二分图的一个性质:
二分图不存在长度为奇数的环
因为每条边都是从一个集合到另一个集合,如果要回到一个集合那只能走偶数次
这种方法是把所有的点分成两种颜色(对应两种集合),如果这张图是二分图,那么每条边连接的两个点的颜色
都应该是不同的
所以我们从第一个点开始,把它染成\(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都会把连通的一整部分搜完,当然也不可能搜到之前的点啦
其实染色法判断的就是:同一集合有没有边相连