temp   4달 전

혼자 이분매칭을 공부하고 있습니다.

그런데 정말 이해가 되지 않는 부분이 있어 질문을 드립니다.

요 이분매칭 소스에서 

visited 배열과 backMatch 배열은 정확히 무얼 의미하나요?

처음에는 visited는 시작하는 집합으로생각했는데 소스보면 도착하는 녀석을 의미하는것 같기도하고..

backMatch는 전혀 모르겠습니다 ㅠㅠ

그리고 11번째줄과 12번째줄이 전혀 이해가 되지 않습니다. ㅠㅠ

무슨말인가요?

keh0711   4달 전

backMatch[next] ==-1는 아직 어떠한 정점과도 매칭되지 않았다는 것을 의미합니다.

만약 매칭이 되지 않았다면 backMatch[next]에는 현재 정점을 매칭시킵니다. backMatch[next]=now 요렇게


만약 backMatch[next] -1이 아니란 것은 이미 next가 다른 정점과 연결된 것을 의미합니다.

그래서 || dfs(backMatch[next])의 backMatch[next]는 next와 연결된 정점으로 가서 해당 정점이 next와 연결 외에도 다른 정점과 연결가능하다면 return true로 돌려주고 next는 now와 다시 맺어줍니다.


댓글을 작성하려면 로그인해야 합니다.