一般图最大匹配(带花树算法)
复杂度
cpp
struct Graph {
int n;
std::vector<std::vector<int>> e;
Graph(int n) : n(n), e(n) {}
void addEdge(int u, int v) {
e[u].push_back(v);
e[v].push_back(u);
}
std::vector<int> findMatching(int m, const auto &init) {
std::vector<int> match(n, -1), vis(n), link(n), f(n), dep(n);
for (auto [x, y] : init) {
match[x] = y;
match[y] = x;
}
// disjoint set union
auto find = [&](int u) {
while (f[u] != u)
u = f[u] = f[f[u]];
return u;
};
auto lca = [&](int u, int v) {
u = find(u);
v = find(v);
while (u != v) {
if (dep[u] < dep[v])
std::swap(u, v);
u = find(link[match[u]]);
}
return u;
};
std::queue<int> que;
auto blossom = [&](int u, int v, int p) {
while (find(u) != p) {
link[u] = v;
v = match[u];
if (vis[v] == 0) {
vis[v] = 1;
que.push(v);
}
f[u] = f[v] = p;
u = link[v];
}
};
// find an augmenting path starting from u and augment (if exist)
auto augment = [&](int u) {
while (!que.empty())
que.pop();
std::iota(f.begin(), f.end(), 0);
// vis = 0 corresponds to inner vertices, vis = 1 corresponds to outer vertices
std::fill(vis.begin(), vis.end(), -1);
que.push(u);
vis[u] = 1;
dep[u] = 0;
int y = -1;
while (!que.empty()){
int u = que.front();
que.pop();
if (u >= m) {
y = u;
}
for (auto v : e[u]) {
if (vis[v] == -1) {
vis[v] = 0;
link[v] = u;
dep[v] = dep[u] + 1;
// found an augmenting path
if (match[v] == -1) {
for (int x = v, y = u, temp; y != -1; x = temp, y = x == -1 ? -1 : link[x]) {
temp = match[y];
match[x] = y;
match[y] = x;
}
return;
}
vis[match[v]] = 1;
dep[match[v]] = dep[u] + 2;
que.push(match[v]);
} else if (vis[v] == 1 && find(v) != find(u)) {
// found a blossom
int p = lca(u, v);
blossom(u, v, p);
blossom(v, u, p);
}
}
}
if (y != -1) {
for (int x = -1, temp; y != -1; x = temp, y = x == -1 ? -1 : link[x]) {
temp = match[y];
if (x != -1) {
match[x] = y;
}
match[y] = x;
}
}
};
// find a maximal matching greedily (decrease constant)
// auto greedy = [&]() {
// for (int u = 0; u < n; ++u) {
// if (match[u] != -1)
// continue;
// for (auto v : e[u]) {
// if (match[v] == -1) {
// match[u] = v;
// match[v] = u;
// break;
// }
// }
// }
// };
// greedy();
for (int u = 0; u < m; ++u)
if (match[u] == -1)
augment(u);
return match;
}
};
void solve(){
int n,m;
cin>>n>>m;
vector<array<int,2>> edges(m);
Graph g(n);
for(auto &[x,y]:edges)cin>>x>>y,x--,y--,g.addEdge(x,y);
int ans=0;
auto match=g.findMatching(n,vector<array<int,2>>{});
for(int i=0;i<n;i++)ans+=match[i]!=-1;
cout<<ans/2<<"\n";
for(int i=0;i<n;i++){
cout<<match[i]+1<<" \n"[i==n-1];
}
}