POJ 1719最大匹配

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

我的代码：

Source Code

Problem: 1719   User: bingshen
Memory: 1160K   Time: 16MS
Language: C++   Result: Accepted

Source Code
#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 ");
   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 ");
   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(" ");
  }
}
return 0;
}

补充：软件开发 , C语言 ,