将棋盘中的一个点当作二分图中的一条边,分别将棋盘中的行和列当作左右子集。
#include<bits/stdc++.h>
using namespace std;
int a[210][210];
int m,n,t;
struct node{
int to;
int next;
}e[400010];
int head[100000],cnt;
void add(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int sum,match[200000];
int vis[200000];
int dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!vis[v]){
vis[v]=1;
if(!match[v] || dfs(match[v])==1){
match[v]=u;
match[u]=v;
return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=t;i++){
int x,y;
scanf("%d%d",&x,&y);
a[x][y]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]) continue;
add(i,j+n);
}
}
for(int i=1;i<=n;i++){
if(!match[i]){
if(dfs(i)==1) sum++;
memset(vis,0,sizeof(vis));
}
}
printf("%d",sum);
}