MATCHING  Fast Maximum Matching
FJ has N (1 ≤ N ≤ 50,000) cows and M (1 ≤ M ≤ 50,000) bulls. Given a list of P (1 ≤ P ≤ 150,000) potential matches between a cow and a bull, compute the greatest number of pairs that can be matched. Of course, a cow can be matched to at most one bull, and vice versa.
Input
The first line contains three integers, N, M, and P. Each of the next P lines contains two integers A (1 ≤ A ≤ N) and B (1 ≤ B ≤ M), denoting that cow A can be matched with bull B.
Output
Print a single integer that is the maximum number of pairs that can be obtained.
Example
Input: 5 4 6 5 2 1 2 4 3 3 1 2 2 4 4 Output: 3
Cow 1 can be matched to bull 2, cow 3 to bull 1, and cow 4 to bull 3.
Note: see also http://www.spoj.com/problems/FASTFLOW/.
hide comments
vincecao:
20171205 12:50:13
always tle made me try every possible way to reduce the time cost, however it resulted in the bug in HK causing the dead loop... 

simp:
20171121 04:06:56
Kuhn will not pass, you should use algorithm HopcroftKarp. 

br4in1:
20171120 16:12:24
simple dp 

Luis Manuel Díaz Barón:
20170529 17:34:09
Kuhn > TLE .... WHY???? Has anyone got AC using Kuhn ?? 

hamzaziadeh:
20161016 21:07:37
ac in 1 go, easy problem for beginners. 

Jeenu Grover:
20160718 09:20:07
@ufrnmaratona Did you find out why are you getting a wrong answer. I have done the same thing and wrong answer. I f possible please give a test case. 

Ashraful Islam:
20160216 22:05:56
please some one help me,i use kuhn's algorithm and get TLE.


dacin21:
20160213 15:43:34
Wait, why does lowest label push relabel pass while highest label is to slow?? (Using a pretty optimized implementation) 

andre schurrle:
20150606 13:43:58
Last edit: 20150615 05:17:33 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150529 00:45:06
From TLE to top 10 fastest _

Added by:  Neal Wu 
Date:  20090412 
Time limit:  0.281s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 