USACO 4.2 The Pefect Stall

Standard bipartite match with Hungarain Algorithm.

#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

int N /* cows */, M /* stalls */;
vector<vector<int>> graph;
vector<int> match;
vector<bool> visited;

void addEdge(int u, int v) {
    graph[u].emplace_back(v);
    graph[v].emplace_back(u);
}

bool dfs(int v) {
    visited[v] = true;
    for (int i = 0; i < graph[v].size(); ++i) {
        int u = graph[v][i], w = match[u];
        if (w < 0 || (!visited[w] && dfs(w))) {
            match[v] = u; match[u] = v;
            return true;
        }
    }
    return false;
}

int bipartite_match() {
    int ans = 0;
    std::fill(match.begin(), match.end(), -1);
    int size = (int)graph.size();
    for (int i = 0; i < size; ++i) {
        if (match[i] >= 0) continue;
        std::fill(visited.begin(), visited.end(), false);
        if (!dfs(i)) continue;
        ++ans;
    }
    return ans;
}

int main() {
    ifstream fin("stall4.in");
    ofstream fout("stall4.out");
    fin >> N >> M;
    int size = N + M + 1;
    graph = vector<vector<int>>(size, vector<int>());
    match = vector<int>(size, -1);
    visited = vector<bool>(size, false);
    int n, k;
    for (int i = 0; i < N; ++i) {
        fin >> n;
        for (int j = 0; j < n; ++j) {
            fin >> k;
            addEdge(i, k + N);
        }
    }

    int ans = bipartite_match();
    cout << ans << endl;
    fout << ans << endl;
}