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 p..
2015. 8. 21. 13:32