题目大意

给出$m$道题，$n$个锦囊妙计，每道题必须使用其对应的两个锦囊妙计之一才能通过，继续去做下一道题，每个锦囊妙计只要用过一次就不能再用，问最多能做完多少道题。

数据范围

$1\leqslant n\leqslant 1000,1\leqslant m\leqslant 1000$

题解

每个问题只要一个锦囊妙计就能通过，每个锦囊妙计只能用一次，很容易想到这就是二分图匹配

把每个问题和对应的两个锦囊妙计连一条边，求一边二分图匹配就行了

注意按照题意，若是有一个问题无法与锦囊妙计匹配就要输出匹配数结束程序了！

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;

int map[1050][1050],link[1050],flag[1050];
int n,m,ans;

int check(int x){
    For(j,0,n-1)
        if ((!flag[j])&&(map[x][j])){
            flag[j]=1;
            if ((!link[j])||(check(link[j]))){link[j]=x;return 1;}
        }
    return 0;
}

int main(){
    scanf("%d%d",&n,&m);
    For(i,1,m){
        int a,b;
        scanf("%d%d",&a,&b);
        map[i][a]=map[i][b]=1;
    }
    For(i,1,m){
        memset(flag,0,sizeof(flag));
        if (check(i)) ans++;
        else break;
    }
    printf("%d\n",ans);
    return 0;
}