62 lines
1.7 KiB
C++
62 lines
1.7 KiB
C++
#include "Graph.h"
|
|
#include <queue>
|
|
#include <algorithm>
|
|
#include <functional>
|
|
|
|
int Graph::checkBipart(std::vector<char>& marks) const {
|
|
marks.assign(n + 1, 0);
|
|
auto nb = toSimpleAdj();
|
|
|
|
std::queue<int> q;
|
|
for (int s = 1; s <= n; ++s) {
|
|
if (marks[s]) continue;
|
|
marks[s] = 'A';
|
|
q.push(s);
|
|
while (!q.empty()) {
|
|
int u = q.front();
|
|
q.pop();
|
|
char opposite = (marks[u] == 'A') ? 'B' : 'A';
|
|
for (int v : nb[u]) {
|
|
if (marks[v] == 0) {
|
|
marks[v] = opposite;
|
|
q.push(v);
|
|
} else if (marks[v] == marks[u]) {
|
|
return 0;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
std::vector<std::pair<int, int>> Graph::getMaximumMatchingBipart() const {
|
|
std::vector<std::pair<int, int>> matching;
|
|
std::vector<char> marks;
|
|
if (!checkBipart(marks)) return matching;
|
|
|
|
auto nb = toSimpleAdj();
|
|
std::vector<int> match(n + 1, 0); // right vertex -> matched left vertex
|
|
std::vector<char> used(n + 1, 0);
|
|
|
|
std::function<bool(int)> augment = [&](int u) -> bool {
|
|
used[u] = 1;
|
|
for (int v : nb[u]) {
|
|
if (marks[v] != 'B') continue;
|
|
if (match[v] == 0 || (!used[match[v]] && augment(match[v]))) {
|
|
match[v] = u;
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
};
|
|
|
|
for (int u = 1; u <= n; ++u) {
|
|
if (marks[u] != 'A') continue;
|
|
std::fill(used.begin(), used.end(), (char)0);
|
|
augment(u);
|
|
}
|
|
for (int v = 1; v <= n; ++v)
|
|
if (match[v] != 0) matching.push_back({match[v], v});
|
|
return matching;
|
|
}
|