호프크로프트 카프 알고리즘 (Hopcroft-Karp Algorithm)

이분매칭 포드 풀커슨  \(O(VE)\)

이분매칭 호프크로프트 카프  \(O(\sqrt{v}E)\)

a->b 형태로 매칭 한다고 하였을 때.

1. 매칭되지 않은 a 정점을 level 0으로 하여 bfs 한다.  

2. b정점이 매칭되어 있고 (matched_b[b]!=-1) 

    해당하는 a 정점의 level이 정해지지 않았다면 (level[matched_b[b]]==-1)

    해당 정점의 level을 갱신한다. (level[matched_b[b]]=level[a]+1)

3. 매칭되지 않은 모든 정점에서 dfs 한다. b정점이 매칭되지 않았거나, 

    매칭된 a정점의 level이 현재 정점 level+1이라면 새로운 증가경로를 탐색한다.

    (matched_b[b]==-1||(level[matched_b[b]]=level[a]+1&&dfs(matched_b[b])))