bipartite graph

이분 매칭

이분 매칭(Bipartite Matching)은 네트워크 플로우의 개념중에서 이분 그래프(Bipartite Graph)에서의 최대 유량을 구하는 경우이다.

DFS를 이용해 이분 매칭을 O(V+E)의 시간 복잡도로 보다 간편하게 구현할 수 있다.

노드를 탐색하며, 각 노드에서 정점으로 연결할 때, 다른 노드가 연결되어 있는 경우

다른 노드를 다른 정점에 연결시키며 연결 할 수 있는 최대 갯수를 구한다.

이때 시작 노드가 바뀔 때마다 방문 여부를 초기화한다.

그래프를 선언할 때, 추정되는 연결 관계만 설정함에 유의한다. (from > to만 설정한다)

int visited[MAX_LENGTH];
int matchingTable[MAX_LENGTH];

vector<vector<int>> graph;

int recursive(int from) {
  if (visited[from]) return false;

  visited[from] = true;

  for (int to : graph[from]) {
    if (matchingTable[to] == 0 || recursive(matchingTable[to])) {
      matchingTable[to] = from;

      return true;
    }
  }
  return false;
}

for (int node = 1; node <= N; node++) {
  memset(visited, 0, sizeof(visited));

  if (recursive(node)) answer++;
}