Some resources found on the Web state that the running time of the bipartite matching algorithm (as found in UL: Undefined's solution) is O(|V|(|V| + |E|)). I suspect, however, that there exists a better upper bound for this. In Problem H of Saratov Regional, the number of the vertices can be as large as 
. A Θ(|V|(|V| + |E|)) algorithm usually gives TLE for graphs of this size, but many participants got ACs by submitting that algorithm.
I suspect the running time is determined by the lesser of the number of vertices on the left and the number of vertices on the right. Am I wrong? I couldn't prove or disprove myself.
Thanks. (It seems I should forget Latin to make room for Russian...) I didn't know the algorithm has a name at all.
Yes, the running time is O(X (|V|+|E|)), where X is the number of vertices on the left. So if we choose left side as smaller side and right side as larger - it will be much faster that vice versa.
Also it's widely known that in reality this upper bound is never reached.
Additionally, there exists a trick, when before executing the DFS you try to find an straight edge to a non-saturated vertex. This trick greatly improves the running time, and makes the algorithm applicable even for thousands of vertices.
more precisely, Kuhn is
, where n1 is a size of left side, and Ans is the result.
Another question is whether this algorithm is called Kuhn's in the literature. After a bit of Googling it seems Kuhn's algorithm usually refers to the one based on matrices.