Maximum bipartite matching - augmenting path algorithm

bipartite_matching.cc

bool extendpath(int x) {
    for (int i = 1; i <= m; ++ i)
        if (edge[x][i] && flag[i]) {
            flag[i] = false;
            if (matching[i] == -1 || extendpath(matching[i])) {
                matching[i] = x;
                return true;
            }
        }
    return false;
}

int max_mathcing() {
    int ans = 0;
    memset(matching, -1, sizeof(matching));
    for (int i = 1; i <= n; ++ i) {
        memset(flag, true, sizeof(flag));
        if (extendpath(i)) ++ ans;
    }
    return ans;
}

bipartite_matching_oo.cc

const int MAXN = 105;

const int MAXV = 4 * MAXN;
const int MAXE = MAXV * MAXV;

class Graph {
public:
    static const int nulledge = -1;
    int V, E;

    Graph(int V) : V(V), E(0) {
        memset(start_u, nulledge, sizeof(start_u));
    }
    void add_edge(int x, int y) {
        edge_v[E] = y; next_edge[E] = start_u[x]; start_u[x] = E; ++ E;
    }

    void add_edge_undirected(int x, int y) {
        add_edge(x, y); add_edge(y, x);
    }

    int start(int u) {
        return start_u[u];
    }

    int next(int e) {
        return next_edge[e];
    }

    int v(int e) {
        return edge_v[e];
    }

private:
    int next_edge[MAXE];
    int edge_v[MAXE];
    int start_u[MAXV];

};

class BipartiteMatching {
public:
    Graph *graph;
    int L, R;

    BipartiteMatching(Graph *graph, int L, int R) : graph(graph), L(L), R(R) {}

    int matching();
    vector<pair<int, int>> get_matchings();

private:
    int m[MAXV];
    bool flag[MAXV];

    bool extend_path(int);
};

vector<pair<int, int>> BipartiteMatching::get_matchings() {
    vector<pair<int, int>> ret;
    for (int r = L; r < L + R; ++ r)
        if (m[r] != -1)
            ret.push_back({m[r], r});
    return ret;
}

bool BipartiteMatching::extend_path(int l) {
    for (int e = graph->start(l); e != Graph::nulledge; e = graph->next(e)) {
        int r = graph->v(e);
        if (flag[r]) {
            flag[r] = false;
            if (m[r] == -1 || extend_path(m[r])) {
                m[r] = l;
                return true;
            }
        }
    }
    return false;
}

int BipartiteMatching::matching() {
    int res = 0;
    memset(m, -1, sizeof(m));
    for (int l = 0; l < L; ++ l) {
        memset(flag, true, sizeof(flag));
        if (extend_path(l)) ++ res;
    }
    return res;
}