学步园

题目连接：http://poj.org/problem?id=1719

很明显的最大匹配题目。而且题目是SPJ的，可以直接用匈牙利算法计算从行到列的最大匹配数

我的代码：

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

bool map[1005][1005];
bool used[1005];
int link[1005];
int n,m;

bool dfs(int u)
{
	int i;
	for(i=1;i<=m;i++)
	{
		if(map[u][i]&&!used[i])
		{
			used[i]=true;
			if(link[i]==-1||dfs(link[i]))
			{
				link[i]=u;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int i,j,x,y,t,num;
	scanf("%d",&t);
	while(t--)
	{
		num=0;
		scanf("%d%d",&n,&m);
		memset(map,0,sizeof(map));
		memset(link,-1,sizeof(link));
		if(n>m)
		{
			printf("NO\n");
			continue;
		}
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			map[x][i]=true;
			map[y][i]=true;
		}
		for(i=1;i<=n;i++)
		{
			memset(used,0,sizeof(used));
			if(dfs(i))
				num++;
		}
		if(num<n)
		{
			printf("NO\n");
			continue;
		}
		else
		{
			for(i=1;i<=m;i++)
			{
				if(link[i]!=-1)
					printf("%d ",link[i]);
				else
				{
					for(j=1;j<=n;j++)
						if(map[j][i])
						{
							printf("%d ",j);
							break;
						}
				}
			}
			printf("\n");
		}
	}
	return 0;
}