DFS를 사용한 Bipartite Maximum Matching

이분 그래프의 정점 집합을 각각 L, R이라고 하자.

아이디어는 역시 alternating path를 찾는 것이다.

match[i] : (L에 속하는 정점 i)가 매칭된, R에 포함되어있는 점. 없으면 -1
rev[j] : (R에 속하는 정점 j)가 매칭된, L에 포함되어있는 점. 없으면 -1

dfs(p)는 p에서 시작하는 alternating path를 찾아, 그 부분을 매칭시키고 true를 return한다.

alternating path가 없다면 false를 return한다.
p에서 시작하는 alternating path를 어떻게 찾을까?

p와 연결된 정점 q를 생각하자.

q가 매칭되지 않았다면 p와 q를 잇고 끝내면 된다.

q가 r과 매칭되었다고 하면, p-q-r과 r에서 시작하는 alternating path를 이으면 또 alternating path가 된다.

def dfs(p):
    p와 연결된 모든 q에 대해:
        q가 체크되어있지 않으면:
            q를 체크
            rev[q]==-1 이거나, (rev[q]≠-1이고 dfs(rev[q]))이면:
                match[p]=q
                return true
    return false

def maximum_match():
    ans=0
    for vertex v in L:
        체크 배열을 초기화
        if dfs(v):

            ++ans

    return ans