이분매칭

blog.naver.com/kks227/220804885235

라이님 블로그에서 공부했음을 밝힙니다.

 

---

설명은 라이님 블로그 정독

 

이분그래프에서 최대 매칭 수를 반환한다.

 

하나의 class의 모든 정점을 돌면서 각 정점마다 최악의 경우 모든 간선을 확인하게 된다.

$O(VE)$

 

Hopcroft-Karp Algorithm($O(E\sqrt{V})$)로 대체 가능하다.

 

<문제>

www.acmicpc.net/problem/17412

 

각 소마다 원하는 축사가 있다. 가장 많은 소를 축사에 배정하라.

 

<풀이>

이분매칭

 

<코드>

const int MAX = 201;

//A[i] : A그룹의 i번째와 매칭된 B그룹의 정점번호
int n, m, A[MAX], B[MAX]; 
vector<int> g[MAX];
bool vst[MAX];

//A그룹의 정점 u를 이분매칭 성공하면 true
bool dfs(int u) {
	vst[u] = true;
	for (int v : g[u]) {
    	//v가 아직 매칭되지 않았거나
        //v가 매칭됐는데 v의 매칭 상대가 아직 방문되지 않았고 새로 매칭 가능하면
		if (B[v] == -1 || (!vst[B[v]] && dfs(B[v]))) {
			A[u] = v;
			B[v] = u;
			return true;
		}
	}
	return false;
}

int main() {
	FAST; cin >> n >> m;
	for (int u = 0; u < n; u++) {
		int cnt; cin >> cnt;
		while(cnt--){
			int v; cin >> v;
			g[u].push_back(v - 1);
		}
	}
	int match = 0;
	memset(A, -1, sizeof(A));
	memset(B, -1, sizeof(B));
	for (int i = 0; i < n; i++) {
		if (A[i] == -1) {
			memset(vst, 0, sizeof(vst));
			if (dfs(i)) match++;
		}
	}
	cout << match << '\n';
}