[Algorithm] 최대 이분 매칭 문제

문제

Given a bipartite undirected graph G=(XUY, E), find the maximum-cardinality matching M*.
주어진 이분 비방향 그래프 G에서 (중복되지 않는) 최대 매칭 집합크기를 구해라.

Matching이란?

A subset M of E is called Matching if no two edges in M are adjacent in G.
E의 부분집합 M에 인접한 두 edge가 존재하지 않는다면, M은 Matching이라고 부른다.

성질

In a bipartite undirected graph G=(XUY,E), if every vertex has degree k>0, then there exists a perfect matching M.
이분 매칭에서 모든 정점이 같은 차수라면, 완전 매칭이 존재한다.

i.e., the maximum-cardinality matching M* satisfies that |M*| = |X| = |Y|
퍼펙트 매칭에서 매칭 최대 개수는 |M*| = |X| = |Y|를 만족한다.

해결방법 1 (최대 유량 문제)

최대 유량 문제로 치환 가능하다 (Ford_Fulkerson, Edmond karp 알고리즘)
1. Generate a source s and a sink t. 시작점 s와 끝점 t를 생성한다.
2. For each x in X, add edge from s to x with capacity 1. s에서 x로 용량 1의 간선을 만든다.
3. For each y in Y, add edge from y to t with capacity 1. y에서 t로 용량 1의 간선을 만든다.
4. For each edge xy in E, add edge from x to y with capacity 1. 모든 xy 간선을 용량 1로 만든다.
5. s에서 t까지 최대한 보낼수 있는 유량을 계산하면, 이는 곧 최대 매칭 개수와 같다.

해결방법 2 (DFS)

// DFS 기반 최대 이분 매칭 코드

#include <vector>

using namespace std;

typedef vector<vector<int>> adjList;

#define N 10 // N = |A| : A 그룹의 크기
#define M 10 // M = |B| : B 그룹의 크기

adjList vt;      // vt[a] : a와 연결된 b들 인접리스트
bool visited[N]; // for all a in A. a를 방문했는가.
int Match[M];    // for all b in B. b와 매칭되는 a의 index.

bool DFS(int a)
{
    if (visited[a])    // 방문한적 있다면 반복하지 않는다.
        return false;  // a는 짝을 못찾았다.
    visited[a] = true; // 방문 체크한다.

    for (int b : vt[a]) // a와 연결된 모든 b에 대해서
    {
        // 만약 짝이 없거나, b의 짝a가 다른 b를 찾을수 있다면
        if (Match[b] == -1 || DFS(Match[b]))
        {
            Match[b] = a; // b의 짝을 현재 a로 바꿔준다.
            return true;  // a는 짝을 찾았다.
        }
    }

    return false; // a는 짝을 못찾았다.
}

int MaxMatching()
{
    int ans = 0; // a와 b의 최대 매칭 개수

    fill(Match, Match + M, -1); // 매칭되지 않은 리스트를 -1로 초기화한다.
    for (int i = 0; i < N; i++) // N을 순회하면서 짝을 찾는다.
    {
        fill(visited, visited + N, false);
        if (DFS(i)) // i번째 a는 짝을 찾았다.
            ++ans;
    }

    return ans;
}