题目链接:二部图
二部图
时间限制: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.
二分图定义:有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中,每个顶点集中没有边相连接!判断二分图的常见方法:开始对任意一未染色的顶点染色,之后判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色, 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图,若颜色不同则继续判断。
错误代码我也要贴出来,因为wa了十几次了,让司老大看也看不出毛病,求大牛指导。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = ;
int color[maxn];
vector<int> g[maxn];
int n,m;
bool dfs(int u,int c){
color[u] = c;
for(int i = ; i<g[u].size(); i++){
if(color[g[u][i]] == c) return false;
if(color[g[u][i]] == && !dfs(g[u][i],-c)) return false;
}
return true;
}
void solve(){
while(scanf("%d%d",&n,&m)!=EOF){
int x,y;
for(int i = ; i<=m; i++){
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
int flag = ;
for(int i = ; i<n; i++){
if(color[i] == ){
if(!dfs(i,)){
flag = ;
break;
}
}
}
if(flag) printf("NOT BICOLORABLE.\n");
else printf("BICOLORABLE.\n");
memset(color,,sizeof(color));
for(int i = ; i<=n; i++) g[i].clear();
}
}
int main()
{
solve();
return ;
}