[BOJ 1867] 돌멩이 제거

이분 매칭 문제

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

 

 

---

[문제 풀이]

 

https://kangwlgns.tistory.com/128

 

---

[소스 코드] / C++

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
vector<int> adj[501];
int B[501];
bool visited[501];

void BtR() {
    for (int i = 0; i < 501; i++) {
        B[i] = -1;
    }
}

void setVisited() {
    for (int i = 1; i < N + 1; i++) {
        visited[i] = false;
    }
}

bool dfs(int cur) {
    visited[cur] = true;

    for (int next : adj[cur]) {
        if (B[next] == -1 || !visited[B[next]] && dfs(B[next])) {
            B[next] = cur;
            return true;
        }
    }

    return false;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    BtR();
    
    int K; cin >> N >> K;
    while (K--) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
    }

    int ans = 0;
    for (int i = 1; i < N + 1; i++) {
        setVisited();
        if (dfs(i)) ++ans;
    }

    cout << ans;
    
    return 0;
}