题目链接：?pid=1015
二部图
时间限制：1000 ms | 内存限制：65535 KB
难度：1
描述
二部图又叫二分图，我们不是求它的二分图最大匹配，也不是完美匹配，，也不是多重匹配，而是证明一个图是不是二部图。证明二部图可以用着色来解决，即我们可以用两种颜色去涂一个图，使的任意相连的两个顶点颜色不相同，切任意两个结点之间最多一条边。为了简化问题，我们每次都从0节点开始涂色
输入输入：多组数据第一行一个整数 n(n<=200) 表示 n个节点第二行一个整数m 表示 条边随后 m行 两个整数 u , v 表示 一条边输出如果是二部图输出 BICOLORABLE.否则输出 NOT BICOLORABLE.样例输入330 11 22 0320 10 2样例输出NOT BICOLORABLE.BICOLORABLE.
【二分图简介】
二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。
准确地说：把一个图的顶点划分为两个不相交集 X和 Y ，使得每一条边都分别连接X 、 Y中的顶点。如果存在这样的划分，则此图为一个二分图。
二分图的一个等价定义是：不含有「奇数条边的环」的图。
图 1 是一个二分图。为了清晰，我们以后都把它画成图 2 的形式。
【思路】
如题目中所给的方法，我们从0节点依此对与他相联的边进行染色，有三种情况
1.如果节点没有染过色，就染上与它相反的颜色，推入队列，
2.如果节点染过色且相反，忽视掉
3.如果节点染过色且与父节点相同，证明不是二分图，return
【代码】
#include<iostream>#include<queue>#include<vector>using namespace std;const int maxn =210;vector<int>G[maxn];int color[maxn];void init(){for(int i=0;i<maxn ;i++){G[i].clear();color[i]=-1;}}bool bicolorable(){//染色法queue<int>Q;color[0]=1;Q.push(0);while(!Q.empty()){int v1 = Q.front();Q.pop();for(int i=0;i<G[v1].size();i++){int v2 =G[v1][i];if(color[v2]==-1){ //情况1color[v2]=-color[v1];Q.push(v2);}else if(color[v2]==color[v1]){ //情况3return false;}}}return true;}int main(){int n,m;while(cin>>n){cin>>m;int a,b;init();for(int i=0;i<m;i++){cin>>a>>b;G[a].push_back(b);G[b].push_back(a);}if(bicolorable())cout<<"BICOLORABLE."<<endl;elsecout<<"NOT BICOLORABLE."<<endl;}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
在时光的激流中，我们总会长大。
