1867번 돌멩이 제거

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

최소 버텍스 커버

이분 매칭

참고할 BOJ 문제

열혈강호

축사 배정

컨닝

룩 어택

영과일 학회방

#include <iostream>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <unordered_map>  
#include <unordered_set>  
#include <tuple>
#include <sstream>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int n = 0, k = 0;
 
int Left[501] = { 0, }; // Left[행] = 열
int Right[501] = { 0, }; // Right[열] = 행
 
vector<int> v[501];
 
bool visit[501] = { false, };
 
// start = 행
bool DFS(int start)
{
    if (visit[start]) return false;
 
    visit[start] = true;
 
    // i는 열
    for (auto i : v[start])
    {
        // 아직 i(열)가 행에 연결되지 않았거나 연결되었더라도 다른 점(다른 행)에 의해 연결될 수 있다면 
        if (Right[i] == -1 || DFS(Right[i]))
        {
            Right[i] = start;
            Left[start] = i;
 
            return true;
        }
    }
 
    return false;
}
 
int bm()
{
    memset(Left, -1, sizeof(Left));
    memset(Right, -1, sizeof(Right));
 
    int ret = 0;
 
    // i는 행
    for (int i = 1; i <= n; i++)
    {
        memset(visit, false, sizeof(visit));
 
        if (DFS(i)) ++ret;
    }
 
    return ret;
}
 
int main(void)
{
    int s = 0, e = 0;
 
    scanf("%d %d", &n, &k);
 
    for (int i = 0; i < k; i++)
    {
        scanf("%d %d", &s, &e);
 
        v[s].push_back(e);
        // v[행].push_back(열);
    }
 
    printf("%d\n", bm());
 
    return 0;
}