## Matching in a general graph

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
ReynaldoGil
Posts: 38
Joined: 7 years ago
Location: Santiago de Cuba
Gender:

### Matching in a general graph

Does anybody know about an efficient implementation of an algorithm for solving this problem? I mean an implementation short enough to be written during a contest...

ReynaldoGil
Posts: 38
Joined: 7 years ago
Location: Santiago de Cuba
Gender:

### Re: Matching in a general graph

Thanks mukel, I've been looking for it a long time, I'll let you know if I translate it, anyway some days ago I found this one, but I don't know wether it works or not

Code: Select all

``````#include <iostream>
#include <cstring>
using namespace std;

const int nMax = 250;
const bool black = false;
const bool red = true;

int n;
int arSize;
int nUnUsed;

bool a[nMax][nMax];
bool color[nMax][nMax];
bool viewed[nMax][nMax];
bool unUsed[nMax];
bool curViewed[nMax];
int vertex[nMax];
int ar[nMax];

void init()
{
for(int i = 0; i < n; i++)
unUsed[i] = true;
}

int findNextFree(int findFrom)
{
int i = findFrom;
while (i < n && !unUsed[i]) i++;
if (i == n) return -1;
else return i;
}

void initAr()
{
nUnUsed = 0;
memset(curViewed, 0, sizeof curViewed);
memset(viewed, 0, sizeof viewed);
}

bool initAllStop;
bool initNext(int index, int from, bool addnew)
{
int parent = vertex[index - 1];
int i = from;
while (i <= nAdj[parent] - 1 &&
(
!(
index + 1 == 1 ||
(index + 1 == 2 && color[Adj[parent][i]][parent] == black) ||
(index + 1 > 2 && color[Adj[parent][i]][parent] != color[parent][vertex[index - 2]])
)
)
)
i++;
if (i > nAdj[parent] - 1)
{
i = from;
while ((i <= nAdj[parent] - 1) &&
(
(!((index + 1 == 1) ||
((index + 1 == 2) && (color[Adj[parent][i]][parent] == black)) ||
((index + 1 > 2) && (color[Adj[parent][i]][parent] != color[parent][vertex[index - 2]]))
))
))
i++;
}
else initAllStop = true;
if (i <= nAdj[parent] - 1)
{
{
if (unUsed[vertex[index]])
nUnUsed--;
curViewed[vertex[index]] = false;
}
nUnUsed++;
ar[index] = i;
}
return (i <= nAdj[parent] - 1);
}

void initAll()
{
bool cont = true;
initAllStop = false;
int i = arSize  - 1 + 1;
while (cont && !initAllStop)
{
cont = initNext(i, 0, true);
i++;
if (cont) arSize++;
}
}

bool doStep()
{
bool cont = true;
while ((cont) && (arSize > 0))
{
bool res = initNext(arSize  - 1, ar[arSize  - 1] + 1, false);
if (res)
{
initAll();
cont = false;
}
else
{
curViewed[vertex[arSize  - 1]] = false;
if ((unUsed[vertex[arSize  - 1]]) && (arSize > 1))
nUnUsed--;
arSize--;
}
}
return (arSize > 0);
}

void writeAr()
{
for (int i = 0; i < arSize; i++)
{
cout << vertex[i];
if (i != arSize - 1)
cout << " ";
}
cout << endl;
}

bool findString()
{
int findFrom = 0;
bool fin  = false;
bool noFree = false;
while (!fin && !noFree)
{
int start = findNextFree(findFrom);
findFrom = start + 1;
noFree = (start == -1);
if (!noFree && nAdj[start] > 0)
{
initAr();
arSize = 1;
vertex[arSize - 1] = start;
ar[arSize - 1] = -1;
curViewed[start] = true;
initAll();
bool cont = true;
fin = arSize > 0 && nUnUsed > 0;
while (cont && !fin)
{
cont = doStep();
fin = arSize > 0 && nUnUsed > 0;
}
}
}
if (!noFree)
{
int end = arSize - 1;
while ((end > 0) && (color[vertex[end]][vertex[end - 1]] != black))
end--;
bool fin2 = false;
int i = 0;
while (i <= end && !fin2)
{
unUsed[vertex[i]] = false;
if (i > 0)
{
if (i % 2 == 1)
{
color[vertex[i]][vertex[i - 1]] = red;
color[vertex[i - 1]][vertex[i]] = red;
}
else
{
color[vertex[i]][vertex[i - 1]] = black;
color[vertex[i - 1]][vertex[i]] = black;
}
}
i++;
}
}
return (!(noFree));
}

void writeList()
{
int cnt = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (color[i][j] == red)
cnt += 2;
cout << cnt << endl;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (color[i][j] == red)
cout << i << " " << j  << endl;
}

void solve()
{
init();
bool chk = true;
while (chk)
chk = findString();
writeList();
}

void clearA()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
a[i][j] = false;
}
}

{
if (!a[p1][p2])
{
a[p1][p2] = true;
a[p2][p1] = true;
}
}

void initData()
{
cin >> n;
n++;
clearA();
int p1, p2;
while (!(cin.eof()))
{
cin >> p1 >> p2;
}
/*
n = 222;
clearA();
for (int i = 0; i < n * n; i++)
addCon(rand() % n, rand() % n);
*/
}

int main()
{
initData();
solve();
return 0;
}
``````

xshaka
Posts: 10
Joined: 7 years ago
Gender:

### Re: Matching in a general graph

Actually, there is a known efficient algorithm for this problem: Edmonds algorithm (Edmonds not Edmonds-Karp, since that last one is for max flow). The idea is to build an arbitrary matching and then the algorithm improves it to make it maximum. Here you have my own implementation.

Code: Select all

``````struct edge {
int v, nx;
};
const int MAXN = 1000, MAXE = 2000;
edge graph[MAXE];
int last[MAXN], match[MAXN], px[MAXN], base[MAXN], N, M, edges;
bool used[MAXN], blossom[MAXN], lused[MAXN];
inline void add_edge(int u, int v) {
graph[edges] = (edge) {v, last[u]};
last[u] = edges++;
graph[edges] = (edge) {u, last[v]};
last[v] = edges++;
}
void mark_path(int v, int b, int children) {
while (base[v] != b) {
blossom[base[v]] = blossom[base[match[v]]] = true;
px[v] = children;
children = match[v];
v = px[match[v]];
}
}
int lca(int a, int b) {
memset(lused, 0, N);
while (1) {
lused[a = base[a]] = true;
if (match[a] == -1)
break;
a = px[match[a]];
}
while (1) {
b = base[b];
if (lused[b])
return b;
b = px[match[b]];
}
}
int find_path(int root) {
memset(used, 0, N);
memset(px, -1, sizeof(int) * N);
for (int i = 0; i < N; ++i)
base[i] = i;
used[root] = true;
queue<int> q;
q.push(root);
register int v, e, to, i;
while (!q.empty()) {
v = q.front(); q.pop();
for (e = last[v]; e >= 0; e = graph[e].nx) {
to = graph[e].v;
if (base[v] == base[to] || match[v] == to)
continue;
if (to == root || (match[to] != -1 && px[match[to]] != -1)) {
int curbase = lca(v, to);
memset(blossom, 0, N);
mark_path(v, curbase, to);
mark_path(to, curbase, v);
for (i = 0; i < N; ++i)
if (blossom[base[i]]) {
base[i] = curbase;
if (!used[i]) {
used[i] = true;
q.push(i);
}
}
} else if (px[to] == -1) {
px[to] = v;
if (match[to] == -1)
to = match[to];
used[to] = true;
q.push(to);
}
}
}
return -1;
}
void build_pre_matching() {
register int u, e, v;
for (u = 0; u < N; ++u)
if (match[u] == -1)
for (e = last[u]; e >= 0; e = graph[e].nx) {
v = graph[e].v;
if (match[v] == -1) {
match[u] = v;
match[v] = u;
break;
}
}
}
void edmonds() {
memset(match, 0xff, sizeof(int) * N);
build_pre_matching();
register int i, v, pv, ppv;
for (i = 0; i < N; ++i)
if (match[i] == -1) {
v = find_path(i);
while (v != -1) {
pv = px[v], ppv = match[pv];
match[v] = pv, match[pv] = v;
v = ppv;
}
}
}
``````

whodunit
Posts: 1
Joined: 7 years ago
Gender:

### Re: Matching in a general graph

Hi xshaka
Can you please explain me this code? Where do I give my graph? Do I need to make main class for taking input? And what are all the methods that I call?