hdu 2444 交叉染色判断二分图+二分最大匹配

/*1A 31ms*/
#include<stdio.h>
#include<string.h>
#define N 300
int n;
struct node {
int u,v,next;
}bian[N*N*2];
int color[N],vis[N],link[N],visit[N],ma[N][N],f[N],head[N],yong;
void addedge(int u,int v) {
bian[yong].u=u;
bian[yong].v=v;
bian[yong].next=head[u];
head[u]=yong++;
}
void init() {//初始化
    memset(ma,0,sizeof(ma));
    memset(f,0,sizeof(f));
    memset(visit,0,sizeof(visit));
    memset(link,-1,sizeof(link));
    memset(color,0,sizeof(color));
    memset(vis,0,sizeof(vis));
    memset(head,-1,sizeof(head));
    yong=0;
}
int ff(int u) {//二分匹配
int i;
for(i=1;i<=n;i++)
    if(visit[i]==0&&ma[u][i]) {
        visit[i]=1;
        if(link[i]==-1||ff(link[i])) {
            link[i]=u;
            return 1;
        }
    }
    return 0;
}
int find(int u,int f) {//交叉染色判定
int i;
for(i=head[u];i!=-1;i=bian[i].next) {
    int v=bian[i].v;
    if(f)
       ma[u][v]=1;//建立邻接矩阵
    else
        ma[v][u]=1;
    if(!vis[v]) {
        color[v]=!color[u];
        vis[v]=1;
        find(v,f^1);
    }
    else
        if(color[v]==color[u])return 0;
}
return 1;
}
int main() {
    int m,i,a,b,ok;
    while(scanf("%d%d",&n,&m)!=EOF) {
            init();
        while(m--) {
            scanf("%d%d",&a,&b);
            addedge(a,b);
            addedge(b,a);
            f[a]=f[b]=1;//存在
        }
        ok=0;
    for(i=1;i<=n;i++)
        if(!vis[i]&&f[i]) {
            color[i]=1;
            vis[i]=1;
            if(find(i,1)==0)
                ok=1;
        }
        if(ok) {//是否存在不能交叉染色的
            printf("No
");
            continue;
        }
      b=0;
for(i=1;i<=n;i++) {//二分最大匹配
    memset(visit,0,sizeof(visit));
    b+=ff(i);
}
printf("%d
",b);
    }
return 0;
}