Bipartite Graph

Matching

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;

vector<int> g[N];
int from[N], tot, use[N];
int color[N];
vector<int> leftSide;

bool match(int x) {
    for (int v: g[x]) {
        if (!use[v]) {
            use[v] = 1;
            if (from[v] == -1 || match(from[v])) {
                from[v] = x;
                return 1;
            }
        }
    }
    return 0;
}

int hungary() {
    tot = 0;
    memset(from, -1, sizeof from);
    for (int u: leftSide) {
        memset(use, 0, sizeof use);
        if (match(u)) ++tot;
    }
    return tot;
}

int colorit(int x, int c) {
    if (use[x]) {
        if (color[x] == c) return 0;
        else throw 3;
    } use[x] = 1;
    color[x] = c;
    for (int y: g[x]) {
        colorit(y, c ^ 1);
    }
    return 0;
}

int main() {
    int n; scanf("%d", &n);
    int m; scanf("%d", &m);
    for (int i = 1; i <= n; ++i)
        g[i].clear();
    for (int i = 0; i < m; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(use, 0, sizeof use);
    for (int i = 1; i <= n; ++i)
        if (!use[i]) colorit(i, 1);
    leftSide.clear();
    for (int i = 1; i <= n; ++i)
        if (color[i] == 1) leftSide.push_back(i);
    int tot = hungary();
    printf("%d\n%d\n", tot, n - tot);
    return 0;
}