Cod sursa(job #2430478)

Utilizator freak93Adrian Budau freak93 Data 15 iunie 2019 00:31:35
Problema Cuplaj maxim in graf bipartit Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cassert>
#include <cstring>
#include <cstdio>

using namespace std;

class Graph {
  public:
    Graph(int size_left, int):
        m_edges(size_left) {}

    void add_edge(int from, int to) {
        m_edges[from].push_back(to);
    }

    int size() const {
        return m_edges.size();
    }

    vector< pair<int, int> > match() {
        memset(m_left, -1, sizeof(m_left));
        memset(m_right, -1, sizeof(m_right));

        //for (auto &edges : m_edges)
        //    random_shuffle(edges.begin(), edges.end());

        while (true) {
            memset(m_used, 0, sizeof(m_used));
            bool try_again = false;
            for (int i = 0; i < size(); ++i)
                if (m_left[i] == -1)
                    try_again = (try_again || go(i));
            if (!try_again)
                break;
        }

        vector< pair<int, int> > match;
        for (int i = 0; i < size(); ++i)
            if (m_left[i] != -1)
                match.emplace_back(i, m_left[i]);
        return match;
    }

  private:
    bool go(int node) {
        if (m_used[node])
            return false;
        m_used[node] = true;

        for (auto &next : m_edges[node])
            if (m_right[next] == -1 || go(m_right[next])) {
                m_left[node] = next;
                m_right[next] = node;
                return true;
            }
        return false;
    }

    vector< vector<int> > m_edges;
    int m_used[10005];
    int m_left[10005];
    int m_right[10005];
};

int main() {
    freopen("cuplaj.in", "r", stdin);
    freopen("cuplaj.out", "w", stdout);

    ios::sync_with_stdio(false);

    //ifstream cin("cuplaj.in");
    //ofstream cout("cuplaj.out");

    int N, M, E; cin >> N >> M >> E;
    Graph G(N, M);
    for (int i = 0; i < E; ++i) {
        int x, y; cin >> x >> y;
        G.add_edge(x - 1, y - 1);
    }

    auto match = G.match();
    cout << match.size() << "\n";
    for (auto &p : match)
        cout << p.first + 1 << " " << p.second + 1 << "\n";
}