1 #include
     
       2 #include
      
        3 #include
       
         4 #define M 1005 5 using namespace std; 6 int pi[M],n,m,a[M][2],f[M],i; 7 bool xun(int a1) 8 { 9     for(int j=0;j<2;j++)10       if(!f[a[a1][j]])11         {12             f[a[a1][j]]=1;13             if(!pi[a[a1][j]]||xun(pi[a[a1][j]]))14               {15                 pi[a[a1][j]]=a1;16                 return 1;17               }18         }19     return 0;20 }21 int main()22 {23     scanf("%d%d",&n,&m);24     for( i=1;i<=m;i++)25       {26         scanf("%d%d",&a[i][0],&a[i][1]);27         a[i][0]++;28         a[i][1]++;29       }30     for( i=1;i<=m;i++)31       {32         memset(f,0,sizeof(f));33         if(!xun(i))34           break;35       }36     printf("%d\n",i-1);37 }
       
      
     

二分图匹配，每个题读入两个锦囊，将题到两个锦囊连边，然后顺序进行比配，直到无法匹配时退出。