백준[2188] 축사 배정

문제 설명

문제 링크

http://icpc.me/2188

2188번: 축사 배정

풀이

이분매칭 연습문제다.

이분 매칭에 대한 설명은 여기를 참고해라.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 202;
vector<int> v[N];
bool visited[N]; // 왼쪽 집합의 i를 방문했는지 여부
int l[N]; // 왼쪽 집합의 i가 연결된 놈
int r[N]; // 오른쪽 집합의 i가 연결된 놈

bool dfs(int a) {
    visited[a] = true;
    for (auto b : v[a]) {
        // b가 연결된게 없거나, b에 이미 연결된 놈을 방문 안했고, 
        // dfs로 들어가면 이미 연결된놈을 방문처리 해서 건너뛰고 다른놈에 연결
        if (r[b] == -1 || !visited[r[b]] && dfs(r[b])) {
            r[b] = a;
            l[a] = b;
            return true;
        }
    }
    return false;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int s; cin >> s;
        v[i].resize(s);
        for (auto &k : v[i]) cin >> k;
    }
    fill(r, r + N, -1);
    fill(l, l + N, -1);
    
    int ret = 0;
    for (int i = 0; i < n; i++) {
        fill(visited, visited + N, false);
        if (dfs(i)) ret++;
    }
    
    cout << ret;
}