AcWing 861. 二分图的最大匹配
原题链接
简单
作者:
huaqingren
,
2021-02-10 15:35:19
,
所有人可见
,
阅读 263
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main
{
private static int N=510;
private static int M=100010;
private static List<Integer>[] g=new ArrayList[N];
private static int n1,n2,m;
private static boolean[] st=new boolean[N];
private static int[] match=new int[N];
public static void main(String[] args)
{
Scanner scan=new Scanner(System.in);
n1=scan.nextInt();
n2=scan.nextInt();
m=scan.nextInt();
for(int i=1;i<=n1;i++)
g[i]=new ArrayList<>();
while(m--!=0)
{
int a=scan.nextInt();
int b=scan.nextInt();
g[a].add(b);
}
int res=0;
for(int i=1;i<=n1;i++)
{
for(int j=1;j<=n2;j++)
st[j]=false;
if(find(i))
res++;
}
System.out.println(res);
scan.close();
}
private static boolean find(int x)
{
for(int i=0;i<g[x].size();i++)
{
int j=g[x].get(i);
if(!st[j])
{
st[j]=true;
if(match[j]==0||find(match[j]))
{
match[j]=x;
return true;
}
}
}
return false;
}
}