[질문] 이분매칭 알고리즘이 이상함;;

[ㅁㄴㅇ(211.59)]

↑ 요거슨 종만북에 나온 이분매칭 코드

위에 그래프를 최대매칭 시켜보면 

딱봐도 

(파랑0 주황1) 

(파랑1 주황0) 

해서 최대 플로우는 2가 되야되는거 아님?

근데 돌려보면 

Step 1. 파랑0을 매칭

a. 파랑0과 주황0을 매치함

b. 파랑0의 visited 를 True 로 업데이트

Step 2. 파랑1을 매칭

a. 파랑1 의 유일한 대상인 주황0 은 이미 선점되있음.

b. 그래서 주황0 의 짝인 파랑0으로 dfs(파랑0) 을 돌려보니 이미 visited[파랑0] 이 참이라서 꺼지셈ㅂㅂ 하고 리턴당함

c. 파랑1은 그대로 아무하고도 매칭되지 못한채 함수끝남

그래서 총 값이 1나옴;; 2가 안나오고. 이거 뭐가 잘못된거임?

원래는 스텝 2에서 

파랑0이 주황0에서 주황1로 갈아타고

이제 주황0 비었으니까 파랑1이 주황0이랑 매치되야되는거 아님?

[옥토끼(moonrabbit2)]

visited는 한번 매칭시도하고 초기화해야함 - dc App

[ㅁㄴㅇ(211.59)]

아 그러네 ㅅㅂ 나도 방금봄 ㄳ