11375번 열혈강호

이분 매칭 문제이다.

81번 째 줄을 조심하자.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
#define MAX 1000
 
int Connection[MAX][MAX] = { -1, };
 
int work[MAX] = { -1, }; // 인덱스는 일
int person[MAX] = { -1, }; // 인덱스는 사람
 
int visit[MAX] = { -1, };
 
int Work = 0, Person = 0; // 위의 배열 2개(work, person) 대소문자 조심할 것.
 
int DFS(int start)
{
    if (visit[start] == 1) return -1;
 
    visit[start] = 1;
 
    for (int i = 0; i < Work; i++)
    {
        if (Connection[start][i] == 1)
        {
            if (work[i] == -1 || DFS(work[i]) == 1)
            {
                work[i] = start;
                person[start] = i;
 
                return 1;
            }
        }
    }
 
    return -1;
}
 
int BipartiteMatching()
{
    memset(work, -1, sizeof(work));
    memset(person, -1, sizeof(person));
 
    int Size = 0;
 
    for (int i = 0; i < Person; i++)
    {
        memset(visit, -1, sizeof(visit));
 
        if (DFS(i) == 1) ++Size;
    }
 
    return Size;
}
 
int main(void)
{
    memset(Connection, -1, sizeof(Connection));
 
    scanf("%d %d", &Person, &Work);
 
    for (int i = 0; i < Person; i++)
    {
        int canWork_Cnt = 0;
 
        scanf("%d", &canWork_Cnt);
 
        for (int j = 0; j < canWork_Cnt; j++)
        {
            int canWork = 0;
 
            scanf("%d", &canWork);
 
            --canWork; // 누락 조심
 
            Connection[i][canWork] = 1; // i번 째 직원이 ,canWork번 일을 할 수 있다.
        }
    }
 
    printf("%d\n", BipartiteMatching());
 
    return 0;
}