[알고리즘 소개]
이분 그래프에서 최대 매칭을 구하는 알고리즘
[코딩 방법]
- A, B그룹이 어디에 매칭됐는지를 기록할 A[i], B[i], dfs마다 쓸 visited[i], 인접그래프 2차원 배열 adj (A는 안 쓰는 경우가 많음)
- 인접그래프를 채워주고 A그룹의 모든 정점들에 대해 dfs를 시작. 시작 전에 visited는 전부 false로 초기화
- 재귀에 들어오면 먼저 visited[cur]을 true로 변환
- cur의 모든 인접한 정점인 next에 대해 if (B[next] == -1 || !visited[B[next]] && dfs(B[next])이면 B[next] = cur, A[cur] = next로 바꾸고 true반환
- 그렇지 않다면 false반환.
- 재귀를 마치고 true가 돌아왔으면 매칭 성공
[시간 복잡도]
O(V * E)
[공부용 링크]
'정리 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 정점 선인장 (0) | 2023.09.23 |
|---|---|
| [알고리즘] 쾨닉의 정리 (Kőnig's theorem) (0) | 2023.02.27 |
| [알고리즘] 마나허 (Manacher) (0) | 2023.02.26 |
| [알고리즘] KMP (0) | 2023.02.05 |
| [알고리즘] 이분 탐색 (Binary Search) (0) | 2023.01.15 |
