二部图（广搜染色）

描述

二部图又叫二分图，我们不是求它的二分图最大匹配，也不是完美匹配，也不是多重匹配，而是证明一个图是不是二部图。证明二部图可以用着色来解决，即我们可以用两种颜色去涂一个图，使的任意相连的两个顶点颜色不相同，切任意两个结点之间最多一条边。为了简化问题，我们每次都从0节点开始涂色

输入

输入：
多组数据
第一行一个整数 n(n<=200) 表示 n个节点
第二行一个整数m 表示 条边
随后 m行 两个整数 u , v 表示 一条边

输出

如果是二部图输出 BICOLORABLE.否则输出 NOT BICOLORABLE.

样例输入

330 11 22 0320 10 2

样例输出

NOT BICOLORABLE.BICOLORABLE.

tips:染色判断二分图，广搜一下即可

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
int n,m;
vector<int>g[222];
int col[222];
bool bfs()
{
queue<int>q;
q.push(0);col[0]=1;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=0;i<g[x].size();i++)
{
int nx=g[x][i];
if(!col[nx]){
col[nx]=col[x]==1?2:1;
q.push(nx);
}
else{
if(col[nx]==col[x])return false;
}
}
}
return true;
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
memset(col,0,sizeof(col));
for(int i=0;i<=n;i++)g[i].clear();
for(int i=0;i<m;i++)
{
int x,y;scanf("%d %d",&x,&y);
g[x].push_back(y);g[y].push_back(x);
}
if(bfs()){puts("BICOLORABLE.");}
else puts("NOT BICOLORABLE.");
}
return 0;
}

最后

以上就是粗暴面包为你收集整理的二部图（广搜染色）的全部内容，希望文章能够帮你解决二部图（广搜染色）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。