백준 11375번: 열혈강호 (C++)

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

11375번: 열혈강호

---

Solved By: Bipartite Matching

#include <iostream>
#include <vector>
#include <memory.h>
#define MAX 1001
using namespace std;

int n, m;
vector<int> adj[MAX];
bool visited[MAX];
int occupy[MAX];

bool dfs(int node){
    for(int i = 0; i < adj[node].size(); i++){
        int next = adj[node][i];
        
        if(visited[next]) continue;
        visited[next] = true;
        
        if(occupy[next] == 0 || dfs(occupy[next])){
            occupy[next] = node;
            return true;
        }
    }
    return false;
}

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

int main(){
    cin >> n >> m;
    
    int a;
    for(int i = 1; i <= n; i++){
        int v; cin >> v;
        for(int j = 0; j < v; j++){
            cin >> a;
            adj[i].push_back(a);
        }
    }
    
    int result = 0;
    for(int i = 1; i <= n; i++){
        init();
        if(dfs(i)) result++;
    }
    
    cout << result;
    return 0;
}