Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 5c5923d

Browse filesBrowse files
bqi343bqi343
committed
new unweighted matching
1 parent 1a782e9 commit 5c5923d
Copy full SHA for 5c5923d

File tree

Expand file treeCollapse file tree

4 files changed

+140
-0
lines changed
Filter options
Expand file treeCollapse file tree

4 files changed

+140
-0
lines changed

‎Implementations/content/graphs (12)/Matching/GeneralMatchBlossom.h

Copy file name to clipboard
+68Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
/**
2+
* Description: Variant on Gabow's Impl of Edmond's Blossom Algorithm.
3+
* General unweighted max matching with 1-based indexing. If
4+
* \texttt{white[v] = 0} after \texttt{solve()} returns, \texttt{v} is part
5+
* of every max matching.
6+
* Time: O(NM), faster in practice
7+
* Source:
8+
* https://github.com/koosaga/DeobureoMinkyuParty
9+
* https://www-m9.ma.tum.de/graph-algorithms/matchings-blossom-algorithm/index_en.html
10+
* https://codeforces.com/blog/entry/63630
11+
* https://github.com/yosupo06/library-checker-problems/blob/master/graph/general_matching/sol/correct.cpp
12+
* https://web.eecs.umich.edu/~pettie/matching/Gabow-general-matching-1976.pdf
13+
* Verification:
14+
* https://codeforces.com/contest/1089 B
15+
* https://www.codechef.com/problems/HAMILG
16+
* https://judge.yosupo.jp/problem/general_matching
17+
*/
18+
19+
struct MaxMatching {
20+
int N; V<vi> adj;
21+
V<int> mate, first; vb white; vpi label;
22+
void init(int _N) { N = _N; adj = V<vi>(N+1);
23+
mate = first = vi(N+1); label = vpi(N+1); white = vb(N+1); }
24+
void ae(int u, int v) { adj.at(u).pb(v), adj.at(v).pb(u); }
25+
int group(int x) { if (white[first[x]]) first[x] = group(first[x]);
26+
return first[x]; }
27+
void match(int p, int b) {
28+
swap(b,mate[p]); if (mate[b] != p) return;
29+
if (!label[p].s) mate[b] = label[p].f, match(label[p].f,b); // vertex label
30+
else match(label[p].f,label[p].s), match(label[p].s,label[p].f); // edge label
31+
}
32+
bool augment(int st) { assert(st);
33+
white[st] = 1; first[st] = 0; label[st] = {0,0};
34+
queue<int> q; q.push(st);
35+
while (!q.empty()) {
36+
int a = q.ft; q.pop(); // outer vertex
37+
each(b,adj[a]) { assert(b);
38+
if (white[b]) { // two outer vertices, form blossom
39+
int x = group(a), y = group(b), lca = 0;
40+
while (x||y) {
41+
if (y) swap(x,y);
42+
if (label[x] == pi{a,b}) { lca = x; break; }
43+
label[x] = {a,b}; x = group(label[mate[x]].first);
44+
}
45+
for (int v: {group(a),group(b)}) while (v != lca) {
46+
assert(!white[v]); // make everything along path white
47+
q.push(v); white[v] = true; first[v] = lca;
48+
v = group(label[mate[v]].first);
49+
}
50+
} else if (!mate[b]) { // found augmenting path
51+
mate[b] = a; match(a,b); white = vb(N+1); // reset
52+
return true;
53+
} else if (!white[mate[b]]) {
54+
white[mate[b]] = true; first[mate[b]] = b;
55+
label[b] = {0,0}; label[mate[b]] = pi{a,0};
56+
q.push(mate[b]);
57+
}
58+
}
59+
}
60+
return false;
61+
}
62+
int solve() {
63+
int ans = 0;
64+
FOR(st,1,N+1) if (!mate[st]) ans += augment(st);
65+
FOR(st,1,N+1) if (!mate[st] && !white[st]) assert(!augment(st));
66+
return ans;
67+
}
68+
};

‎Implementations/content/graphs (12)/Matching/GeneralMatchBlossom_Alt.h

Copy file name to clipboard
+72Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
/**
2+
* Description: Variant on Gabow's Impl of Edmond's Blossom Algorithm.
3+
* General unweighted max matching with 1-based indexing. If \texttt{repr[v] = 0}
4+
* after \texttt{solve()} returns, \texttt{v} is part of every max matching.
5+
* Time: O(N^3), faster in practice
6+
* Source:
7+
* https://github.com/koosaga/DeobureoMinkyuParty
8+
* https://www-m9.ma.tum.de/graph-algorithms/matchings-blossom-algorithm/index_en.html
9+
* https://codeforces.com/blog/entry/63630
10+
* https://github.com/yosupo06/library-checker-problems/blob/master/graph/general_matching/sol/correct.cpp
11+
* https://web.eecs.umich.edu/~pettie/matching/Gabow-general-matching-1976.pdf
12+
* Verification:
13+
* https://codeforces.com/contest/1089 B
14+
* https://www.codechef.com/problems/HAMILG
15+
* https://judge.yosupo.jp/problem/general_matching
16+
*/
17+
18+
struct GeneralMaxMatch {
19+
int N; V<vi> adj;
20+
vi mate, lca_aux, par, repr;
21+
void init(int _N) { N = _N; adj = V<vi>(N+1);
22+
mate = lca_aux = par = repr = vi(N+1); }
23+
void ae(int x, int y) { assert(0 < min(x,y));
24+
adj.at(x).pb(y), adj.at(y).pb(x); }
25+
int get_repr(int x) { // first ancestor without par set
26+
if (par[repr[x]]) assert(repr[x] != x), repr[x] = get_repr(repr[x]);
27+
return repr[x]; // path compression
28+
}
29+
int get_lca(int x, int y) { // get lca of x and y in O(dist)
30+
static int timer = 0;
31+
for (++timer;;swap(x,y)) {
32+
if (x == 0) continue;
33+
x = get_repr(x); assert(!par[x]);
34+
if (lca_aux[x] == timer) return x;
35+
lca_aux[x] = timer; x = par[mate[x]];
36+
}
37+
}
38+
bool augment(int src) {
39+
queue<int> q; q.push(repr[src] = src);
40+
auto compress = [&](int x, int y, int lca) { assert(repr[lca]);
41+
while (get_repr(x) != lca) {
42+
int mx = mate[x];
43+
if (get_repr(x) == x) { assert(!par[x] && !repr[mx]);
44+
repr[x] = repr[mx] = lca, q.push(mx);
45+
} else assert(repr[mx]);
46+
par[x] = y; x = par[y = mx];
47+
}
48+
};
49+
while (sz(q)) {
50+
int x = q.ft; q.pop(); assert(repr[x]);
51+
for (int y: adj[x]) { int my = mate[y];
52+
if (repr[y]) { // compress the tree (blossom)
53+
int lca = get_lca(x,y);
54+
compress(x,y,lca), compress(y,x,lca);
55+
} else if (!my) { // found augmenting path!
56+
for (par[y] = x;y;) swap(mate[mate[y] = par[y]],y);
57+
par = repr = vi(N+1); // reset par and repr
58+
return true;
59+
} else if (!repr[my]) {
60+
par[y] = x, repr[my] = my, q.push(my);
61+
}
62+
}
63+
}
64+
return false;
65+
}
66+
int solve() {
67+
int ans = 0;
68+
FOR(i,1,N+1) if (!mate[i]) ans += augment(i);
69+
FOR(i,1,N+1) if (!mate[i] && !repr[i]) assert(!augment(i));
70+
return ans;
71+
}
72+
};

‎Implementations/content/graphs (12)/Matching/UnweightedMatch.h renamed to ‎Implementations/content/graphs (12)/Matching/GeneralMatchBlossom_Old.h

Copy file name to clipboard
File renamed without changes.

‎Implementations/content/graphs (12)/Matching/UnweightedMatch2.h renamed to ‎Implementations/content/graphs (12)/Matching/GeneralMatchDet.h

Copy file name to clipboard
File renamed without changes.

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.