C++ – Maximum matching of bipartite graph

It is agreed that the edge storage method is a directed edge from the left to the right, and the left and right vertices have the same number.

Hungarian algorithm

lli mch[maxn];
lli vis[maxn];

bool dfs_hun(lli u, lli dfn) {
    if (vis[u] == dfn) return false;
    vis[u] = dfn;
    for (lli i = head[u]; ~i; i = edge[i].nxt) {
        lli v = edge[i].v;
        if (mch[v] == 0 || dfs_hun(mch[v], dfn)) {
            mch[v] = u;
            return true;
        }
    }
    return false;
}

lli ask_hun() {
    lli res = 0;
    for (lli i = 1; i <= n; ++i)
        if (dfs_hun(i, i))
            ++res;
    return res;
}

Post Reply