문제

https://www.acmicpc.net/problem/11375


알고리즘

이분 매칭


풀이

존재하는 정점을 두 가지 그룹으로 나누었을 때, 간선의 양 끝점 정점이 서로 다른 그룹에 속해있는 그래프를 이분 그래프라고 하고, 이분 그래프상에서 최대 매칭을 구하는 문제를 이분 매칭이라고 합니다.

기본적인 이분매칭 문제로, 전체적인 구현은 프로그래밍 콘테스트 챌린징의 이분매칭 구현을 참고하였습니다. 핵심인 $dfs$ 함수는 현재 정점(사람)의 간선을 검사하는데 만약 반대 정점(일)이 매칭이 되지 않았거나, 매칭 되었더라도 해당 매칭을 옮길 수 있으면 true를 리턴하게 됩니다. 이로써 최대 매칭에 성공하게 되는 것이죠. 각 정점에 대해 $dfs$를 수행하므로 시간 복잡도는 $O(VE)$입니다.

코드

#include <bits/stdc++.h>
#include <unordered_set>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, M,cnt,what;
int match[1001];
bool visited[1001];
vector<vector<int>> adj;

bool dfs(int here) {
    visited[here] = true;
    for (auto there : adj[here]) {
        int u = match[there];
        if (!u || !visited[u] && dfs(u)) {
            match[there] = here;
            return true;
        }
    }
    return false;
}

int bipartite_matching() {
    int ret = 0;
    REP(i, N) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i)) ++ret;
    }
    return ret;
}

int main() {
    FAST;
    cin >> N >> M;
    adj.resize(N + 1);
    REP(i, N) {
        cin >> cnt;
        while (cnt--) {
            cin >> what;
            adj[i].emplace_back(what);
        }
    }
    cout << bipartite_matching();

    return 0;
}