백준 2188번: 축사 배정 (C++)

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

2188번: 축사 배정

---

Solved By: Bipartite Matching

 

전형적인 이분 매칭 이론 문제였습니다.

+ 이번 문제를 계기로 Bipartite Matching, O(VE)를 스스로 구현할 수 있게 되었습니다.

#include <iostream>
#include <vector>
#include <memory.h>
#define MAX 201
using namespace std;

vector<int> adj[MAX];
bool visited[MAX];
int occupy[MAX];
int n, m;

bool biMatch(int node){
    for(int i = 0; i < adj[node].size(); i++){
        int next = adj[node][i];
        
        if(visited[next]) continue;
        visited[next] = true;
        
        if(occupy[next] == 0 || biMatch(occupy[next])){
            occupy[next] = node;
            return true;
        }
    }
    
    return false;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int v; cin >> v;
        for(int j = 0; j < v; j++){
            int a; cin >> a;
            adj[i].push_back(a);
        }
    }
    
    int result = 0;
    for(int i = 1; i <= n; i++){
        memset(visited, false, sizeof(visited));
        if(biMatch(i)) result++;
    }
    
    cout << result;
    return 0;
}