Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
944 B
3
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define MAXN 505

vector<int> g[MAXN];
int match[MAXN];
bitset<MAXN> vis;

bool Try(int now) {
    for (auto i : g[now]) {
        if (!vis[i]) {
            vis[i] = true;
            if (!match[i] || Try(match[i])) {
                match[i] = now;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u++, v++;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int matchCnt = 0;
    for (int i = 1; i <= n; i++) {
        vis.reset();
        if (Try(i)) matchCnt++;
    }
    cout << matchCnt / 2 << '\n';

    vector<bool> output(n, false);
    for (int i = 1; i <= n; ++i) {
        if (match[i]  && !output[i]) {
            output[match[i]] = true;
            printf("%d %d\n", match[i] - 1, i - 1);
        }
    }
}
Leave a Comment