南阳理工1015 （染色法判断二分图）

二部图

时间限制：1000 ms  |  内存限制：65535 KB

难度：1

描述

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

输入

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

输出

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

样例输入

样例输出

题目就是叫你判断是否为二分图。而且是模拟染色过程。

判断二分图，用染色法就可以。把第一个点颜色标记为黑色，与之相邻的点颜色就为白色，并把这些点加入队列。

重复这个过程。

过程中只会有3种情况

1.如果节点没有染过色，就染上与它相反的颜色，推入队列，

2.如果节点染过色且相反，忽视掉

3.如果节点染过色且与父节点相同，证明不是二分图，结束

#include<iostream>
#include<cstdio>
#include<cstring>
#include<functional>
#include<algorithm>
#include<vector>
#include<queue>
#define maxn 305
using namespace std;
vector<int >maps[maxn];
int color[maxn];
int n,m;
void init()
{
	memset(color,0,sizeof(color));
	for(int i=0;i<=n;i++)
		maps[i].clear();
}
int dyeing()//染色过程
{
	int v1,v2;
	queue<int>que;
	color[0]=1;
	que.push(0);
	while(que.size())
	{
		v1=que.front();
		que.pop();
		for(int i=0;i<maps[v1].size();i++)
		{
			v2=maps[v1][i];
			if(color[v2]==0)//情况1
			{
				color[v2]=-color[v1];
				que.push(v2);
			}
			else if(color[v2]!=0&&color[v2]==color[v1])//情况3
				return 0;
		}
	}
	return 1;
}
int main()
{
	int i,a,b;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			maps[a].push_back(b);//邻接表
			maps[b].push_back(a);//无向图
		}
		if(dyeing())
			printf("BICOLORABLE.\n");
		else
			printf("NOT BICOLORABLE.\n");
	}
}