이분 매칭

이분 매칭

 

두 그룹 A와 B는 서로 연결될 수 있는 두 그래프이다. 이러한 이분 그래프에서 최대 매칭을 찾는 문제를 간단하게

 

이분 매칭이라고 한다.

 

// A 와 B의 정점의 개수
int n, m;

bool adj[MAX_N][MAX_M];

vector<int> aMatch, bMatch;

vector<bool> visited;

int dfs(int a) {
	if (visited[a]) return false;    
	visited[a] = true;
	
	for (int b = 0; b < m; b++) {
		if (adj[a][b]) {

			// 만약 b가 매칭되지 않았을때
			// or 매칭이 되었을 경우 b와 매칭된 A그룹의 정점이   
                        // 다른 B 그룹의 정점과 연결이 가능한지 파악  
			// 가능하다면 그 점과 연결한 후 a 와 b 매칭
			if (bMatch[b] == -1 || dfs(bMatch[b])) {
				// 증가 경로 발견 , a 와 b 매칭
				aMatch[a] = b;
				bMatch[b] = a;
				return true;
			}
		}

	}
	return false;
}

int bipartiteMatch() {
	
	aMatch = vector<int>(n, -1);
	bMatch = vector<int>(m, -1);
	int size = 0;
	for (int start = 0; start < n; start++) {
		visited = vector<bool>(n, false);

		if (dfs(start))
			size++;
	}
	return size;
}