2188번 축사 배정

기본적인 이분 매칭이다.

조금 더 이분 매칭을 활용할 수 있도록, 관련 알고리즘 문제들을 많이 풀어봐야겠다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
#define MAX 200
 
int N = 0, M = 0; // N : 소의 마릿수, M : 축사의 개수
 
int nMatch[MAX] = {-1,}; // 인덱스는 소, 그 값은 매칭된 축사
int mMatch[MAX] = {-1,}; // 인덱스는 축사, 그 값은 매칭된 소
 
vector<int> Connection[MAX];
 
bool visit[MAX] = { false, };
 
bool DFS(int start)
{
    if (visit[start]) return false;
 
    visit[start] = true;
 
    for (auto next : Connection[start]) // start번 소가 원하는 축사를 꺼낸다
    {
        if (mMatch[next] == -1 || DFS(mMatch[next]) )
        {// 그 축사가 아직 배정되지 않았거나, 배정되었다면 다른 소가 매칭할 수 있는지 살펴본다.
 
            mMatch[next] = start; 
            nMatch[start] = next;
 
            return true; // 매칭되었으므로, true 리턴.
        }
    }
 
    return false; // 없으면 매칭할 곳이 없다.
}
 
int bipartiteMatch()
{
    memset(nMatch, -1, sizeof(nMatch));
    memset(mMatch, -1, sizeof(mMatch));
 
    int Size = 0;
 
    for (int i = 0; i < N; i++)
    {
        memset(visit, false, sizeof(visit));
 
        if (DFS(i)) ++Size;
    }
 
    return Size;
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
    {
        int Barn_Cnt = 0;
 
        scanf("%d", &Barn_Cnt);
 
        for (int j = 0; j < Barn_Cnt; j++)
        {
            int Barn = 0;
 
            scanf("%d", &Barn);
 
            --Barn;
 
            Connection[i].push_back(Barn); // j번 째 소가 원하는 Barn번의 축사.
            // 오타 주의 j가 아니라 i다. 바로 윗 줄.
        }
    }
 
    printf("%d\n", bipartiteMatch());
 
    return 0;
}