2196384_ac_0ms_104k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include<stdio.h>
#include<string.h>

bool g[202][202];
int n,m,k,ans;
bool b[202];
int link[202];

bool init()
{
	int _x, _y;
    memset(g,0,sizeof(g));
    memset(link,0,sizeof(link));
    ans=0;
    if(scanf("%d%d",&n,&m)!=2)
		return false;
    for(int i = 1; i <= n; i++)
    {
		scanf("%d",&_x);
		for(int j = 1; j <= _x; j++)
		{
			scanf("%d",&_y);
			g[i][_y] = 1;
		}
		
	}
	return true;
}

bool find(int a)
{
	for(int i = 1; i<= m; i++)
	{
		if(g[a][ i ]==1&&!b[ i ])
		{
			b[ i ]=true;
            if(link[ i ]==0||find(link[ i ]))
			{
				link[ i ]=a;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	while(init())
	{
		for(int i = 1; i <= n; i++)
		{
			memset(b,0,sizeof(b));
			if(find(i))
				ans++;
		}
		printf("%d\n",ans);
	}
	return 1;
}