https://www.luogu.org/problemnew/show/P3386

可以只做一边的匹配

#include
using namespace std;
const int maxN = 1e5 + ;
vector G[maxN];
int match[maxN];
int vis[maxN];
int n, m, e, sum;
int dfs(int u) {

for(int i = ; i < G\[u\].size(); i++) {  
    int v = G\[u\]\[i\];  
    //有路而且没被访问  
    if(!vis\[v\]) {  
        vis\[v\] = ;//标记点i已经访问过

        //如果点i未被配对或者找到了新的配对  
        if(match\[v\] ==  || dfs(match\[v\])) {  
            //更新配对关系  
            match\[v\] = u;  
            return ;  
        }  
    }  
}  
return ;  

}

int main() {
// freopen("testdata.in","r", stdin);
scanf("%d %d %d", &n, &m, &e);
for(int i = ; i < e; i++) { int u, v; scanf("%d %d", &u, &v); if(u > n || v > m) continue; //u总是在左边， 只做u的匹配
// v += 10000;
G[u].push_back(v);//只做一边建单向边
// G[v].push_back(u);
}

memset(match,  , sizeof(match));

for(int i = ; i <= n; i++){  
    memset(vis, , sizeof(vis));  
    if(dfs(i)) {  
        sum++;  
    }  
}  
printf("%d\\n", sum);

}