#1398. 二分图最大匹配

二分图最大匹配

题目描述

给定一个二分图,其左部点的个数为 nn,右部点的个数为 mm,边数为 ee,求其最大匹配的边数。

左部点从 11nn 编号,右部点从 11mm 编号。

输入格式

输入的第一行是三个整数,分别代表 n,mn,mee

接下来 ee 行,每行两个整数 u,vu,v,表示存在一条连接左部点 uu 和右部点 vv 的边。

输出格式

输出一行一个整数,代表二分图最大匹配的边数。

1 1 1
1 1
1
4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1
2

数据范围

对于全部的测试点,保证:

  • 1n,m5001 \le n,m \le 500
  • 1e5×1041 \le e \le 5 \times 10^4
  • 1un1 \le u \le n1vm1 \le v \le m

不保证给出的图没有重边