无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。回路就是环路，也就是判断是否存在奇数环。
判断二分图方法：
用染色法，把图中的点染成黑色和白色。
首先取一个点染成白色，然后将其相邻的点染成黑色，如果发现有相邻且同色的点，那么就退出，可知这个图并非二分图。
求二分图最大匹配：二分图可分为x,y两个集合，以任意一个集合为准求得的匹配数相等。可以不分离x,y集合，当为整体来求，最后结果要减半。
#include <iostream>
using namespace std;
const int M=201;
bool g[M][M];
bool visit[M];
bool flag;
int link[M];
int c[M]; //表示颜色，0表示没访问，1表示黑色，-1表示白色
int n,k;
void dfs(int i,int color)//染色法判断是否是二分图
{
for(int j=1;j<=n;j++)
{
if(g[i][j])
{
if(c[j]==0)
{
c[j]=-color;
dfs(j,-color);
}
else if(c[j]==color)
{
flag=false;
return;
}
if(flag==false)
return ;
}
}
}
bool check()
{
flag=true;
memset(c,0,sizeof(c));
c[1]=1; //设一号点是黑色，与它相邻的都染成白色
dfs(1,1); //从1号点开始
return flag;
}
bool find(int i)
{
int j;
for(j=1;j<=n;j++)
{
if(g[i][j] && !visit[j])
{
visit[j]=true;
if(link[j]==0 || find(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}
int main()
{
int i,j,res;
while(cin>>n>>k)
{
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
res=0;
while(k--)
{
cin>>i>>j;
g[i][j]=g[j][i]=true;
}
if(!check())
{
cout<<"No\n";
continue;
}
for(i=1;i<=n;i++) //以x集合为准找了一遍，又以y集合为准找了一遍，匹配数量增倍。[x]+[y]=n
{
memset(visit,0,sizeof(visit));
if(find(i))
res++;
}
cout<<res/2<<endl;
}
return 0;
}
posted on 2011-09-13 14:18
大大木马 阅读(1195)
评论(0) 编辑 收藏 引用