CodeArchive Matching
General graph matching
This algorithm should run in O(n^2 (nlgn + m) ) O(n (nlgn + m) ) time. I guess if I really have time and don't mind adding I have added 5/6 more lines, I may be able to prune that to O(n (nlgn + m) ) times, but I don't know if my idea works. This program is tested on TCO Round 1, and it passed all 83 test cases. Please test it elsewhere to verify that it works.
Algorithm: As of most matching algorithm, we aim at finding alternating augmenting paths. We do that by building an alternating tree from every unmatched vertex. The special thing is, we may end up with odd cycles. If we can go to a vertex with matched edge, we can goto that vertex via unmatched edge from the other way round the cycle. Essentially, the alternating path is multiplexed. We can strink them into a pseudo node and continue building our alternating tree. I used a union-find set to keep track of pseudo node, so that I can actually strink them but not overdoing it. This code is very long right now, as there are so many cases to take care of. Please optimize it if you find a way.
const int MAX_N = 100;
int n, matched[MAX_N], grp[MAX_N];
vector<int> neighbours[MAX_N];
int find_grp(int v) { return grp[v] = ((grp[v] == v)? v : find_grp(grp[v])); }
inline void merge(int a, int b) { grp[find_grp(a)] = find_grp(b); }
/* The graph is given by the neighbours vector
matched will contains the matching, -1 means not matched
vertices are named from 0 to n-1
grp needed for the blossom group merging
return the size of the matching
*/
int matching() {
int result=-1, found=1, u,v=-1, h,t, a,b, dummy=0, seen[MAX_N]={}, q[MAX_N], prev[MAX_N], fringed[MAX_N];
memset(matched, 0xff, sizeof(matched));
while(found) {
++result;
found = 0;
h=t=0;
for (int i = 0; i < n; ++i) {
grp[i] = i; prev[i] = -1; fringed[i] = 0;
if (matched[i] == -1) { prev[i] = i; fringed[q[t++] = i] = 1; }
}
while(!found && h < t) {
u = q[h++];
for (int i = 0; !found && i < neighbours[u].size(); ++i) {
if ((v = neighbours[u][i]) == matched[u]) continue;
if (fringed[v]) {
if (find_grp(v) == find_grp(u)) continue; // Who cares?
++dummy; // find the common ancestor
for(a=find_grp(u), b=find_grp(v); matched[a] != -1 || matched[b] != -1; ) {
if (seen[b] == dummy) { a=b; break; }
seen[b]=dummy; if(matched[b]!=-1) b = find_grp(prev[matched[b]]);
if (seen[a] == dummy) { b=a; break; }
seen[a]=dummy; if(matched[a]!=-1) a = find_grp(prev[matched[a]]);
}
if (found = (matched[a]==-1&&matched[b]==-1&&a!=b)) break;
if (prev[u] == -1) prev[u] = v; if (prev[v] == -1) prev[v] = u;
for(b=find_grp(u), v=find_grp(v); b != a || v != a; swap(v,b) ) {
if (b == a) continue;
merge(b, a); if(!fringed[b = matched[b]]) { fringed[q[t++] = b] = 1; }
merge(b, a); if(prev[prev[b]] == -1) prev[prev[b]] = b;
b = find_grp(prev[b]);
}
} else if (prev[v]==-1) { prev[v] = u; fringed[q[t++] = matched[v]] = 1; }
}
}
if (found) {
for (int r,p=matched[u] ;p!=-1; r=matched[matched[p]=prev[p]], matched[prev[p]]=p, p=r);
for (int r,p=matched[v] ;p!=-1; r=matched[matched[p]=prev[p]], matched[prev[p]]=p, p=r);
matched[u] = v; matched[v] = u;
}
}
return result;
}
-- Main.MatthewChan - 12 Mar 2006
This algorithm should run in O(n^2 (nlgn + m) ) time. I guess if I really have time and don't mind adding 5/6 more lines, I may be able to prune that to O(n (nlgn + m) ) times, but I don't know if my idea works.
Algorithm: As of most matching algorithm, we aim at finding alternating augmenting paths. We do that by building an alternating tree from every unmatched vertex. The special thing is, we may end up with odd cycles. If we can go to a vertex with matched edge, we can goto that vertex via unmatched edge from the other way round the cycle. Essentially, the alternating path is multiplexed. We can strink them into a pseudo node and continue building our alternating tree. I used a union-find set to keep track of pseudo node, so that I can actually strink them but not overdoing it. This code is very long right now, as there are so many cases to take care of. Please optimize it if you find a way.
const int MAX_N = 100;
int n, matched[MAX_N], grp[MAX_N];
vector<int> neighbours[MAX_N];
int find_grp(int v) { return grp[v] = ((grp[v] == v)? v : find_grp(grp[v])); }
inline void merge(int a, int b) { grp[find_grp(a)] = find_grp(b); }
/* The graph is given by the neighbours vector
matched will contains the matching, -1 means not matched
vertices are named from 0 to n-1
grp needed for the blossom group merging
return the size of the matching
*/
int matching() {
int result=-1, found=1, r,u,v=-1, h,t, a,b, dummy=0, seen[MAX_N]={}, q[MAX_N], prev[MAX_N], fringed[MAX_N];
memset(matched, 0xff, sizeof(matched));
while(found) {
++result;
found = 0;
for (r = 0; r < n; ++r) if (matched[r] == -1) {// try constructing a blossom tree from r
for (int i = 0; i < n; ++i) { grp[i] = i; prev[i] = -1; fringed[i] = 0; }
prev[r] = q[h=t=0] = r;
while(!found && h <= t) {
u = q[h++];
for (int i = 0; !found && i < neighbours[u].size(); ++i) {
if ((v = neighbours[u][i]) == matched[u]) continue;
if (v != r && matched[v] == -1) { prev[v] = u; found = 1; break; }
else if (fringed[v]) {
if (find_grp(v) == find_grp(u)) continue; // Who cares?
++dummy; // find the common ancestor
if (prev[u] == -1) prev[u] = v; if (prev[v] == -1) prev[v] = u;
for(a=find_grp(u), b=find_grp(v); seen[a] != dummy && matched[a] != -1;
seen[a] = dummy, a = find_grp(prev[matched[a]]), swap(a,b) ); // a is the common ancestor
for(b=find_grp(u), v=find_grp(v); b != a || v != a; swap(v,b) ) {
if (b == a) continue;
merge(b, a);
if(!fringed[b = matched[b]]) { fringed[q[++t] = b] = 1; }
merge(b, a);
if (prev[prev[b]] == -1) prev[prev[b]] = b;
b = find_grp(prev[b]);
}
} else if (prev[v]==-1) { prev[v] = u; fringed[q[++t] = matched[v]] = 1; }
}
}
if (found) break;
}
if (found) {
for (int p; prev[v] != r; p = matched[prev[v]], matched[v] = prev[v], matched[prev[v]] = v, v = p);
matched[v] = r; matched[r] = v;
}
}
return result;
}
-- Main.MatthewChan - 11 Mar 2006
