#include"iostream"
#include"stdlib.h"
#include"cstdio"
#define M 420 
using namespace std;
int link[M];
int visited[M]; 
typedef struct node
{
	int adjvex;
	struct node*next; 
} node;
struct vnode
{
	node *first; 
}p[M];
void create_graph(int a,int b)
{
	node *temp=(node*)malloc(sizeof(node));
	temp->adjvex=b;
	temp->next=p[a].first;
	p[a].first=temp; 
} 
int dfs(int x)
{
	int i;
	node *t=p[x].first;
	while(t)
	{
		if(visited[t->adjvex]==0)
		{
			visited[t->adjvex]=1;
			if(link[t->adjvex]==-1||dfs(link[t->adjvex]))
			{
				link[t->adjvex]=x;
				//delete(t); 
				return 1; 
			} 
		}
		t=t->next; 
	} 
	//delete(t); 
	return 0; 
} 
int getmaxmatch(int n)
{
	int i,j,sum=0;
	for(int i=1;i<=n;i++)
	 link[i]=-1;
	for(i=1;i<=n;i++)
	{
		if(!p[i].first) 
		   continue;
		for(j=1;j<=n;j++)
		   visited[j]=0;
		if(dfs(i))
		  sum++; 
	}
	return sum; 
} 
int main()
{
	int cases;
	scanf("%d",&cases);
	while(cases--)
	{
		int m,n;
		int i,j; 
		int a,b; 
		scanf("%d%d",&m,&n);
		for(i=1;i<=n;i++)
		 p[i].first=NULL; 
	    for(i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d",&a);
			for(j=1;j<=a;j++)
			{
				scanf("%d",&b);
				create_graph(i+n,b); 
			} 
		} 
		if(getmaxmatch(m+n)==m) 
		  printf("YES\n");
		else
		  printf("NO\n"); 
	} 
	return 0; 
} 
 

• Re:无语了，邻接表实现竟然超内存，求不超内存邻接表做法 (11) jeff126 2011-02-10 23:28:04