#include<stdio.h>
#include<iostream.h>
#include<string.h>
int map[1005][1005];
int chk[1005];
int match[1005];
int result,m,n;
int dfs(int p) 
{ 
  int i,t; 
  for(i=0;i<n;i++) 
    if((map[p][i]==1) && (chk[i]==0)) 
    { 
       chk[i]=1; 
       t=match[i]; 
       match[i]=p; 
       if(t==-1||dfs(t)) 
          return 1; 
       match[i]=t; 
     } 
  return 0; 
} 
int check() 
{ 
  int i,res=0; 
  memset(match,-1,sizeof(match));
  for(i=0;i<m;i++) 
  { 
    memset(chk,0,sizeof(chk));
    if(dfs(i)==1) res++; 
  } 
  return res; 
} 

int main()
{
    int c;
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d%d",&m,&n);
        int i,j,k;
        for(i=0;i<m;i++)
          for(j=0;j<n;j++)
            map[i][j]=0;
        for(i=0;i<n;i++)
        {
                int a,b;
                scanf("%d%d",&a,&b);
                map[a-1][i]=1;
                map[b-1][i]=1;
        }  
       result=check();
        //for(i=0;i<n;i++)
         //printf("%d ",match[i]);
          //printf("\n");
        if(result==m)
        {
            int i;
            for(i=0;i<n-1;i++) 
            cout<<match[i]+1<<" ";
            cout<<match[n-1]+1<<endl;
        }  
        else cout<<"NO"<<endl;
    }
    return 0;             
}    
/*
20
4 4
2 4
3 4
1 3
1 4
5 5
1 5
2 4
3 4
2 4
2 3
*/

• Re:没道理呀,怎么会错呢,就是二分匹配呀??? (31) 455462586 2011-08-30 22:57:50