[BOJ 백준] 11375번 열혈강호

문제

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

11375번: 열혈강호

접근

 이분 매칭(Bipartite Matching)을 이용하여 문제를 해결하였다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n, m, ans = 0, visit[1010], matchNum[1010] = {0};
vector<int> graph[1010];

int dfs(int num) {
    for (int i : graph[num]) {
        if (!visit[i]) {
            visit[i] = 1;
            if (!matchNum[i] || dfs(matchNum[i])) {
                matchNum[i] = num;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int num, a;
        cin >> num;
        for (int j = 0; j < num; j++) {
            cin >> a;
            graph[i].push_back(a);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) 
            visit[j] = 0;
        ans += dfs(i);
    }
    cout << ans;

    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study