[백준] 1298 노트북의 주인을 찾아서

1298번: 노트북의 주인을 찾아서

문제 확인

 

이분 매칭 그래프에서 최소 버텍스 커버 문제입니다.

 

풀이

 

백준 돌멩이 제거 문제와 동일합니다.

[백준] 1867 돌멩이 제거

학생과 노트북을 이분 매칭 그래프로 작성하고 최소 버텍스 커버 알고리즘을 사용하면 간단하게 풀리는 문제입니다.

 

코드

#include <cstdio>
#include <vector>
#include <memory.h>
using namespace std;
vector <short> graph[501];
short match[501];
bool visit[501];
bool dfs(short i) {
    for (short next : graph[i]) {
        if (visit[next])continue;
        visit[next] = true;
        if (!match[next] || dfs(match[next])) {
            match[next] = i;
            return true;
        }
    }
    return false;
}
int main() {
    int n, m, res = 0;
 
    scanf("%d%d", &n, &m);
    for (short i = 0, s, e; i < m; i++) {
        scanf("%hd%hd", &s, &e);
        graph[s].push_back(e);
    }
    for (short i = 1; i <= n; i++) {
        memset(visit, 0, n + 1);
        if (dfs(i))res++;
    }
    printf("%hd", res);
}