学步园

我自己都不知到是怎么AC的。。。

参考了N多代码才看懂

/*
 * 2444.c
 * 我用了很长时间才搞明白，唉～～
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 222

int N,M;
int f[SIZE][SIZE];
int tag[SIZE];
int match[SIZE];
int c[SIZE];

int DFS(int node,int color)
{
	if(c[node]!=0)
	{
		if(c[node]!=color)
			return 0;
		else
			return 1;
	}
	int i;	
	c[node]=color;
	for(i=1;i<=N;i++)
		if(f[node][i])
			if(!DFS(i,-color))
				return 0;
	return 1;
}

int check(void)
{
	int i;
	for(i=1;i<=N;i++)
		if(c[i]==0 && !DFS(i,1))
			return 0;
	return 1;
}

int hungary(int node)
{
	int i;
	for(i=1;i<=N;i++)
		if(f[node][i] && !tag[i])
		{
			tag[i]=1;
			if(!match[i] || hungary(match[i]))
			{
				match[i]=node;
				return 1;
			}
		}
	return 0;
}

int main(void)
{
	int i,count,t1,t2;
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
#endif
	while(scanf("%d%d",&N,&M)!=EOF)
	{
		memset(f,0,sizeof(f));
		memset(match,0,sizeof(match));
		memset(c,0,sizeof(c));

		for(i=0;i<M;i++)
			scanf("%d%d",&t1,&t2),f[t1][t2]=f[t2][t1]=1;
		
		if(check())
		{
			count=0;
			for(i=1;i<=N;i++)
			{
				memset(tag,0,sizeof(tag));
				if(c[i]==1 && hungary(i))
					count++;
			}
			printf("%d\n",count);
		}
		else
			puts("No");
	}
	return 0;
}