I love this implementation of Edmond's Blossoms :-)
Edmond's Blossoms algorithm give a maximum matching in general graphs (non-bipartite)
CODE
/*
GETS:
V->number of vertices
E->number of edges
pair of vertices as edges (vertices are 1..V)
GIVES:
output of edmonds() is the maximum matching
match[i] is matched pair of i (-1 if there isn't a matched pair)
*/
#include <bits/stdc++.h>
using namespace std;
const int M=500;
struct struct_edge{int v;struct_edge* n;};
typedef struct_edge* edge;
struct_edge pool[M*M*2];
edge top=pool,adj[M];
int V,E,match[M],qh,qt,q[M],father[M],base[M];
bool inq[M],inb[M],ed[M][M];
void add_edge(int u,int v)
{
top->v=v,top->n=adj[u],adj[u]=top++;
top->v=u,top->n=adj[v],adj[v]=top++;
}
int LCA(int root,int u,int v)
{
static bool inp[M];
memset(inp,0,sizeof(inp));
while(1)
{
inp[u=base[u]]=true;
if (u==root) break;
u=father[match[u]];
}
while(1)
{
if (inp[v=base[v]]) return v;
else v=father[match[v]];
}
}
void mark_blossom(int lca,int u)
{
while (base[u]!=lca)
{
int v=match[u];
inb[base[u]]=inb[base[v]]=true;
u=father[v];
if (base[u]!=lca) father[u]=v;
}
}
void blossom_contraction(int s,int u,int v)
{
int lca=LCA(s,u,v);
memset(inb,0,sizeof(inb));
mark_blossom(lca,u);
mark_blossom(lca,v);
if (base[u]!=lca)
father[u]=v;
if (base[v]!=lca)
father[v]=u;
for (int u=0;u<V;u++)
if (inb[base[u]])
{
base[u]=lca;
if (!inq[u])
inq[q[++qt]=u]=true;
}
}
int find_augmenting_path(int s)
{
memset(inq,0,sizeof(inq));
memset(father,-1,sizeof(father));
for (int i=0;i<V;i++) base[i]=i;
inq[q[qh=qt=0]=s]=true;
while (qh<=qt)
{
int u=q[qh++];
for (edge e=adj[u];e;e=e->n)
{
int v=e->v;
if (base[u]!=base[v]&&match[u]!=v)
if ((v==s)||(match[v]!=-1 && father[match[v]]!=-1))
blossom_contraction(s,u,v);
else if (father[v]==-1)
{
father[v]=u;
if (match[v]==-1)
return v;
else if (!inq[match[v]])
inq[q[++qt]=match[v]]=true;
}
}
}
return -1;
}
int augment_path(int s,int t)
{
int u=t,v,w;
while (u!=-1)
{
v=father[u];
w=match[v];
match[v]=u;
match[u]=v;
u=w;
}
return t!=-1;
}
int edmonds()
{
int matchc=0;
memset(match,-1,sizeof(match));
for (int u=0;u<V;u++)
if (match[u]==-1)
matchc+=augment_path(u,find_augmenting_path(u));
return matchc;
}
int main()
{
int u,v;
cin>>V>>E;
while(E--)
{
cin>>u>>v;
if (!ed[u-1][v-1])
{
add_edge(u-1,v-1);
ed[u-1][v-1]=ed[v-1][u-1]=true;
}
}
cout<<edmonds()<<endl;
for (int i=0;i<V;i++)
if (i<match[i])
cout<<i+1<<" "<<match[i]+1<<endl;
}
thanks a lot to boleyn.su
سلام من چند وقت پیش تو یک گروه تلگرام ACM عض بودم که شما هم اونجا ضو بودید ولی من ناخواسته لفت دادم و دیگه نتونستم عضو بشم حالا اگه شما هنوز عضو هستید لینک گروه رو بزارید ایجا تا ما هم دوباره عضو بشیم خیلی ممنون
Thanks, now I see.
Lost in translation:
"Hi I some time ago I was a member telegram that you were a member there, but I did and I missed unwanted Left Party, let's go now if you do not already created links to our Group to become a member again thank you very much".
Why is it so hard for people to write in english?
Thanks brother
Hi, can someone please tell me if the above code is suitable for a weighted matching?
No, it isn't but there is another version of this algorithm that works for weighted graphs.
Thanks for the fast answer! Where do I find that version?
Probably not useful in competitive programming, but check Kolmogorov's implementation and paper.
Note: Python implementation that can be adapted for online contests.
Thanks again! It's not for competition so I'm glad for any usable to implement :)
Can you also provide something written in c++? In the second link there is in return a link for a c++ library, called lemon, including a weighted edmond algorithm. Do you have any experience with that or is there something even better? I did some search and as far as I can suggest this seems to be the best. Boost library does not support a weighted version and NetworkX/NetworkKit are also written in phython. So I assume lemon is the best way to go?
The Blossom 5 looks very good, but to be honest, this is way over my head even I "only" have to implement it. But it looks interesting.
I don't have experience with Lemon but I believe it can be trusted (I couldn't find anything better after a very quick search).
I have experience with NetworkX and if you are fine will calling Python functions from a C++ problem then I suggest you use it (it is really awesome once you get used to it).
BTW, Kolmogorov's implementation is in C++. If you're working on some project, I suggest you use a library with a nice API, but you can also use that implementation.
A good place to test your code.
Input format goes like:
vertex count, edge count
u, v: there's an undirected edge connecting vertex u and v. It's guaranteed that u != v, and no edge would appear twice.
Output format goes like:
The number of edges in the matching.
The vertex matched to each vertex. For unmatched vertex output 0.
Weighted matching can be tested here.
also here :)
Goes into inf loop for the input :
For anyone looking at this code, I proved with this input and it did not get into a infinite loop. I actually got the correct answer instantly:
2
1 3
2 4
Link to a problem where you can use it
Hope it helps :)