#P30861. 二分图的最大匹配
二分图的最大匹配
Description
给定一个二分图,其中左半部包含 $n_1$个点(编号 1∼$n_1$),右半部包含 $n_2$个点(编号 1∼$n_2$),二分图共包含 m条边。 数据保证任意一条边的两个端点都不可能在同一部分中。 请你求出二分图的最大匹配数。 二分图的匹配:给定一个二分图 G,在 G的一个子图 M中,M的边集 {E}中的任意两条边都不依附于同一个顶点,则称 M是一个匹配。 二分图的最大匹配:所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配,其边数即为最大匹配数。Input Format
第一行包含三个整数 $n_1$、 $n_2$和 $m$。 接下来 m行,每行包含两个整数 u和 v,表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。Output Format
输出一个整数,表示二分图的最大匹配数。2 2 4
1 1
1 2
2 1
2 2
2