Pagini recente » Monitorul de evaluare | Cod sursa (job #256531) | Cod sursa (job #2315022)
#include <fstream>
#include <vector>
#define UNDEFINED -1
using namespace std;
class Graph {
private:
int a;
int b;
vector<vector<int>> adjList;
int *leftMatch;
int *rightMatch;
bool *used;
public :
Graph(int a, int b) : a(a), b(b) {
adjList = vector<vector<int>>(a, vector<int>());
leftMatch = new int[a];
rightMatch = new int[b];
fill(leftMatch, leftMatch + a, UNDEFINED);
fill(rightMatch, rightMatch + b, UNDEFINED);
used = new bool[a];
fill(used, used + a, false);
}
void addEdge(int from, int to) {
adjList[from].emplace_back(to);
}
bool normalizeMatching(int i) {
if (used[i]) return false;
used[i] = true;
for (auto node : adjList[i]) {
if (rightMatch[node] == UNDEFINED) {
leftMatch[i] = node;
rightMatch[node] = i;
return true;
}
}
for (auto node : adjList[i]) {
if (normalizeMatching(rightMatch[node])){
leftMatch[i] = node;
rightMatch[node] = i;
return true;
}
}
return false;
}
vector<pair<int, int>> bipartiteMatching() {
bool improve;
do {
improve = false;
fill(used, used + a, false);
for (int i = 0; i < a; ++i) {
if (leftMatch[i] == UNDEFINED) {
improve |= normalizeMatching(i);
}
}
} while (improve);
vector<pair<int, int>> matches;
for (int i = 0; i < a; ++i) {
if (leftMatch[i] != UNDEFINED) {
matches.emplace_back(i + 1, leftMatch[i] + 1);
}
}
return matches;
}
};
int main() {
ifstream cin("cuplaj.in");
ofstream cout("cuplaj.out");
int cardA, cardB, m;
cin >> cardA >> cardB >> m;
Graph g(cardA, cardB);
while (m--) {
int from, to;
cin >> from >> to;
--from;
--to;
g.addEdge(from, to);
}
vector<pair<int, int>> matching = g.bipartiteMatching();
cout << matching.size() << "\n";
for (auto pair : matching) {
cout << pair.first << " " << pair.second << "\n";
}
return 0;
}