二部图(染色法判断二部图)

偏执的太偏执、 2022-06-08 01:23 209阅读 0赞

二部图  
时间限制：1000 ms  |  内存限制：65535 KB  
难度：1  
描述  
二部图又叫二分图，我们不是求它的二分图最大匹配，也不是完美匹配，也不是多重匹配，而是证明一个图是不是二部图。证明二部图可以用着色来解决，即我们可以用两种颜色去涂一个图，使的任意相连的两个顶点颜色不相同，切任意两个结点之间最多一条边。为了简化问题，我们每次都从0节点开始涂色  
输入  
输入：  
多组数据  
第一行一个整数 n(n<=200) 表示 n个节点  
第二行一个整数m 表示 条边  
随后 m行 两个整数 u , v 表示 一条边  
输出  
如果是二部图  
输出 BICOLORABLE.  
否则输出 NOT BICOLORABLE.  
样例输入  
3  
3  
0 1  
1 2  
2 0  
3  
2  
0 1  
0 2

输出  
NOT BICOLORABLE.  
BICOLORABLE.

\#include<iostream>  
\#include<queue>  
\#include<cstdio>  
\#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\]=0;  
 \}  
\}

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\];  
   //printf("v2=%d:\\n",color\[v2\]);  
   if(color\[v2\]==0)\{  
    color\[v2\]=-color\[v1\];  
    //printf("v2=%d ",color\[v2\]);  
    Q.push(v2);  
   \}  
   else if(color\[v2\]==color\[v1\])\{  
    return 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;  
  else  
   cout<<"NOT BICOLORABLE."<<endl;  
 \}  
 return 0;  
\}