⚙️AlgorithmAdvanced

General Matching - Blossom Algorithm

Key Points

•
Edmonds' Blossom Algorithm finds a maximum matching in any undirected graph, not just bipartite ones.
•
It detects odd cycles (blossoms) and contracts them so that a usual augmenting-path search can continue.
•
The classic implementation runs in O( $V^{3}$ ) time, which is typically O( $V^{2}$ E) for sparse graphs.
•
The core ideas are alternating paths, least common ancestor (LCA) of blossoms, and careful base updates during contraction.
•
Unlike bipartite graphs, Konig’s theorem does not hold, so maximum matching is not equal to minimum vertex cover in general graphs.
•
A perfect matching exists if and only if Tutte’s condition holds, which generalizes Hall’s theorem.
•
From a maximum matching you can build a minimum edge cover in any graph without isolated vertices in linear time.
•
In contests, Blossom is heavier to implement than Hopcroft–Karp, but it solves problems with odd cycles that bipartite methods cannot.

Prerequisites

→Graph representations (adjacency lists, degrees) — You must be comfortable building and traversing graphs to implement BFS-based alternating trees and neighbor scans.
→Basic matchings and augmenting paths — Understanding alternating and augmenting paths is the foundation of all matching algorithms, including Blossom.
→Bipartite matching (e.g., Hopcroft–Karp) — Gives intuition for alternating BFS layering and why odd cycles complicate general graphs.
→Breadth-first search (BFS) — Blossom grows alternating trees with BFS and uses queue-based exploration.
→Union-Find and LCA ideas (conceptual) — While Blossom’s LCA is custom, the idea of finding a common ancestor and contracting structures is similar to DSU/LCA techniques.
→Proof techniques in combinatorics — To appreciate correctness (e.g., Tutte–Berge formula) and contraction invariants.

Detailed Explanation

Tap terms for definitions

01Overview

General matching in graphs asks: how many disjoint edges can we select so that no two share a vertex? In bipartite graphs, this is solved efficiently by algorithms like Hopcroft–Karp using clean layerings. But real-world relationships are often non-bipartite: triangles and odd cycles appear naturally. Edmonds’ Blossom Algorithm extends augmenting-path methods to general (non-bipartite) graphs by handling odd cycles. The key insight is that when a breadth-first search for an augmenting path encounters an odd cycle, you can temporarily contract the entire cycle into a single super-vertex (a "blossom") and continue searching. If you eventually find an augmenting path in the contracted graph, you can expand the blossom and lift the path back to the original graph.

Practically, the algorithm maintains matchings, parents along alternating trees, and a base for each vertex (its blossom representative). When a potential augmenting path is blocked by an odd cycle, the algorithm identifies the least common ancestor (LCA) of two vertices in alternating trees, marks the blossom, contracts it, and resumes the search. This preserves correctness because augmenting paths exist in the original graph if and only if they exist in the contracted one. The classical implementation has O(V^3) time, suitable up to a few hundred vertices in competitive programming, and is a foundational tool in combinatorial optimization.

02Intuition & Analogies

Imagine trying to pair students for a project so that as many students as possible get a partner. If the class splits cleanly into two groups (e.g., coders and designers), pairing across groups is straightforward with standard bipartite matching. But real classes don’t split so cleanly—friend groups can form triangles: Alice wants to work with Bob, Bob with Carol, and Carol with Alice. This triangle is an odd cycle. If you try to run a simple augmenting-path search, this odd cycle can make you loop around undecidedly.

Blossom’s move is like temporarily treating that tight-knit friend trio as a single “super-student.” You zip the triangle up into one unit. Once zipped, you can continue searching for a partner for this super-student just like any other student. If you find a better pairing path that reaches this super-student, you unzip the triangle and route the path through the correct edges so that only one of the three takes an external partner and the others remain paired internally in the best way. This is safe because inside that triangle there’s always a consistent way to flip pairings along the cycle to accommodate the external connection.

Operationally, you grow alternating trees from unmatched vertices. Edges alternately go unmatched–matched–unmatched, etc. When you hit a conflict that reveals an odd cycle, you identify the cycle’s root with an LCA trick, mark all vertices belonging to the cycle, and shrink it. The search then proceeds as if the cycle were a single vertex. If you eventually find a path to a free vertex, you flip the matched/unmatched status along the path—this increases the total number of matched pairs by one. Rinse and repeat until no augmenting path exists.

03Formal Definition

Let G = (V, E) be a simple undirected graph. A matching M

\subseteq

E is a set of edges no two of which share a vertex. A maximum matching is a matching of largest cardinality

∣

∣

. An alternating path with respect to M is a path whose edges alternate between E

∖

M and M. An augmenting path is an alternating path that starts and ends at unmatched (free) vertices; augmenting along it increases

∣

∣

by one. In bipartite graphs, the Hopcroft–Karp layer structure ensures that if no augmenting path exists, the matching is maximum. For general graphs, odd cycles can hide augmenting paths. A blossom is an odd cycle C in which, relative to an alternating tree grown from an unmatched root, the cycle edges alternate between unmatched and matched, with exactly one "base" vertex incident to an unmatched tree edge leading outside the cycle. Edmonds’ Blossom Algorithm maintains alternating forests and, upon detecting such an odd cycle during BFS, contracts its vertices into a single base vertex. Contraction preserves the existence of augmenting paths: G has an augmenting path with respect to M if and only if the contracted graph does. Repeating searches and contractions until no augmenting path is found yields a maximum matching by Edmonds’ Augmenting Path Theorem generalized to non-bipartite graphs. Formally, correctness is underpinned by Tutte–Berge formula and blossom-shrinking invariants. The classical implementation finds augmenting paths via BFS over alternating trees, detects blossoms using a least common ancestor (LCA) operation in the forest, marks blossom vertices, contracts them by relabeling bases, and continues the search. When an augmenting path is discovered in the contracted graph, it is lifted to the original graph by expanding blossoms and flipping along the corresponding lifted alternating path.

04When to Use

Use Blossom when your graph is not bipartite or you cannot easily enforce a bipartition. Common scenarios include pairing with compatibility constraints that create triangles (e.g., social networks, team formation with mutual preferences), conflict graphs where nodes represent tasks and edges represent “can be paired,” molecule matching in chemistry graphs, and general graph problems that reduce to maximum cardinality matching (e.g., finding minimum edge cover via matching, or checking for the existence of a perfect matching).

In competitive programming, choose Blossom when: (1) you detect odd cycles or the input is explicitly general; (2) Hopcroft–Karp is not applicable; (3) you need maximum cardinality, not maximum weight (the weighted version is Blossom’s more complex cousin). Typical constraints are up to n ≈ 300–600, where O(V^3) is acceptable. For larger n, specialized heuristics or problem structure may be needed.

Do not use Blossom when the graph is bipartite—Hopcroft–Karp is simpler and faster O(E \sqrt{V}). Also avoid it when you only need a greedy near-maximum solution for huge sparse graphs; a heuristic might suffice. If the problem is about weighted matchings, consider Edmonds’ maximum weight matching (a more intricate algorithm with dual variables), or reduce to bipartite weighted matching if possible.

⚠️Common Mistakes

• Treating the graph as bipartite when it is not: applying Hopcroft–Karp will fail to find augmenting paths hidden by odd cycles. Verify bipartiteness or directly use Blossom. • Mishandling blossom contraction logic: forgetting to update bases, queue membership, or parent pointers during contraction leads to missed augmenting paths or infinite loops. Always recompute bases for all vertices inside the blossom and ensure they are enqueued if newly discovered. • Incorrect LCA computation in alternating trees: the LCA here is over base vertices of the current alternating forest, not a static tree LCA. Implement the walk-up marking method carefully using a time-stamped visited array. • Confusing 0-based and 1-based indexing: Blossom code is pointer-heavy; an off-by-one can silently corrupt matchings. • Not handling multi-components: you must start searches from every unmatched root; the graph can be disconnected. • Ignoring self-loops or parallel edges: prune self-loops; parallel edges are harmless but redundant. • Expecting Kőnig’s theorem to hold: in general graphs, maximum matching size is not equal to minimum vertex cover size. Don’t attempt to recover a min vertex cover from the matching as you would in bipartite graphs. • Forgetting isolated vertices when constructing a minimum edge cover: a valid edge cover cannot exist if an isolated vertex is present; check and report impossibility or adjust the problem interpretation.

Key Formulas

Augmenting Path Theorem (informal)

If no augmenting path exists w.r.t. M, then M is maximum.

Explanation: In any graph, if you cannot find an augmenting path relative to a matching M, then M is already maximum. Blossom ensures we can search correctly even in non-bipartite graphs.

Matching Number

α^{'} (G) = max {∣ M ∣ : M is a matching in G}

Explanation: The matching number $α$ '(G) is the size of a maximum matching. Many problems reduce to computing $α$ '(G).

Tutte's Theorem

G has a perfect matching ⟺ \forall S \subseteq V : o (G - S) \leq ∣ S ∣

Explanation: A graph has a perfect matching if and only if for every vertex subset S, the number of odd components o(G−S) of the remaining graph is at most |S|. This generalizes Hall’s theorem beyond bipartite graphs.

Tutte–Berge Formula

ν (G) = \frac{1}{2} U \subseteq V min (∣ V ∣ - (o (G - U) - ∣ U ∣)) = \frac{∣ V ∣ - max _{U \subseteq V} ( o ( G - U ) - ∣ U ∣ )}{2}

Explanation: The size of a maximum matching $ν$ (G) can be computed from the maximum, over all vertex subsets U, of the deficit between odd components and $∣ U ∣$ . This is theoretical and underlies correctness of blossom-shrinking.

Minimum Edge Cover Size

∣ C_{min} ∣ = ∣ V ∣ - ∣ M_{ma x} ∣

Explanation: In any graph without isolated vertices, the minimum edge cover size equals the number of vertices minus the size of a maximum matching. Constructively, start from a maximum matching and add one incident edge for each unmatched vertex.

Time Complexity

T (V, E) = O (V^{3}) (classical Edmonds)

Explanation: The standard unweighted Blossom implementation runs in cubic time in the number of vertices. For sparse graphs this is often described as O( $V^{2}$ E), and is acceptable up to a few hundred vertices.

Space Complexity

S (V, E) = O (V + E)

Explanation: The algorithm stores the graph and several O(V) arrays (match, base, parent, queue flags), yielding linear space in the size of the input graph.

Complexity Analysis

Edmonds’ Blossom Algorithm for maximum cardinality matching proceeds by repeatedly searching for augmenting paths using BFS over alternating forests, while contracting blossoms (odd alternating cycles) that block the search. Each BFS attempt either finds an augmenting path, increasing the matching size by 1, or certifies that no augmenting path exists from that root under the current contractions. The crux of the O(

V^{3}

) bound is: (1) Each augmentation increases the matching size by 1, so there are at most O(V) augmentations. (2) Each augmenting-path search can be implemented in O(

V^{2}

) using adjacency scans and array-based operations; blossom detection and contraction (LCA computation, marking, base updates, queue management) take O(V) per event, and there are O(V) such events per search, totaling O(

V^{2}

) per BFS. Combining these yields O(V) augmentations × O(

V^{2}

) per

a ug m e n t a t i o n = O (V^{3}

). For sparse graphs the bound is commonly written O(

V^{2}

E), since scanning all neighbors across all BFS steps contributes an E factor, while the number of contractions and base relabels multiplies by O(V). Space usage is O(V + E). We maintain the input adjacency list, matching array match[ ], parent pointers p[ ], base representatives base[ ], per-vertex flags used[ ] and blossom[ ], and a queue for BFS. Contractions are handled implicitly by redirecting bases rather than explicitly rebuilding the graph, which keeps memory overhead linear. In practice, well-engineered implementations comfortably handle V up to ~500–1000 with E up to a few 10^5 depending on constants. Performance bottlenecks typically come from repeated neighbor scans and blossom-handling logic; careful pruning of self-loops and duplicate edges, and using compact vectors, can significantly improve runtime.

Code Examples

Edmonds' Blossom: Maximum Matching in a General Graph (read input, print pairs)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Edmonds' Blossom algorithm for maximum cardinality matching in general graphs.
5 // Complexity: O(V^3) in the classical implementation.
6 // Vertices are 0..n-1.
7 
8 struct Blossom {
9     int n;
10     vector<vector<int>> g;           // adjacency list
11     vector<int> match, p, base;      // match[v], parent in alternating tree, base representative
12     vector<int> q;                   // BFS queue
13     vector<bool> used, blossom;      // used in BFS, marks vertices in current blossom
14     vector<int> lca_mark;            // time-stamped marks for LCA
15     int lca_timer = 0;
16 
17     Blossom(int n): n(n), g(n) {}
18 
19     void add_edge(int u, int v) {
20         if (u == v) return; // ignore self-loops
21         g[u].push_back(v);
22         g[v].push_back(u);
23     }
24 
25     int lca(int a, int b) {
26         // Compute least common ancestor of a and b in alternating forest.
27         // We walk up through bases and matched/parent pointers.
28         ++lca_timer;
29         // Mark ancestors of a
30         while (true) {
31             a = base[a];
32             lca_mark[a] = lca_timer; // mark base(a)
33             if (match[a] == -1) break; // reached root of this tree
34             a = p[match[a]]; // go to parent of matched partner
35         }
36         // Walk up from b until we hit a marked base
37         while (true) {
38             b = base[b];
39             if (lca_mark[b] == lca_timer) return b;
40             if (match[b] == -1) break;
41             b = p[match[b]];
42         }
43         return -1; // should not happen
44     }
45 
46     void markPath(int v, int b, int x) {
47         // Mark all vertices on path v -> b in the alternating tree, setting blossom[]
48         // and redirecting parents so contraction can proceed.
49         while (base[v] != b) {
50             blossom[base[v]] = blossom[base[match[v]]] = true;
51             p[v] = x;
52             x = match[v];
53             v = p[match[v]];
54         }
55     }
56 
57     int findPath(int root) {
58         used.assign(n, false);
59         p.assign(n, -1);
60         iota(base.begin(), base.end(), 0); // base[v] = v
61         q.clear(); q.reserve(n);
62         q.push_back(root);
63         used[root] = true;
64         for (size_t qi = 0; qi < q.size(); ++qi) {
65             int v = q[qi];
66             for (int u : g[v]) {
67                 if (base[v] == base[u] || match[v] == u) continue; // ignore trivial cases
68                 if (u == root || (match[u] != -1 && p[match[u]] != -1)) {
69                     // Found a blossom with base cur_lca
70                     int cur_lca = lca(v, u);
71                     blossom.assign(n, false);
72                     markPath(v, cur_lca, u);
73                     markPath(u, cur_lca, v);
74                     // Contract: set base[] to cur_lca for all in blossom, and enqueue new vertices
75                     for (int i = 0; i < n; ++i) {
76                         if (blossom[base[i]]) {
77                             base[i] = cur_lca;
78                             if (!used[i]) {
79                                 used[i] = true;
80                                 q.push_back(i);
81                             }
82                         }
83                     }
84                 } else if (p[u] == -1) {
85                     // Expand alternating tree
86                     p[u] = v;
87                     if (match[u] == -1) {
88                         // Found augmenting path ending at u
89                         return u;
90                     } else {
91                         // Add the matched partner to the queue as an even-level vertex
92                         int w = match[u];
93                         if (!used[w]) {
94                             used[w] = true;
95                             q.push_back(w);
96                         }
97                     }
98                 }
99             }
100         }
101         return -1; // no augmenting path from this root
102     }
103 
104     int solve() {
105         match.assign(n, -1);
106         p.assign(n, -1);
107         base.resize(n);
108         used.assign(n, false);
109         blossom.assign(n, false);
110         lca_mark.assign(n, 0);
111         int matching = 0;
112         for (int v = 0; v < n; ++v) {
113             if (match[v] == -1) {
114                 int u = findPath(v);
115                 if (u == -1) continue; // no augmenting path from v
116                 // Augment along v..u using p[] and match[]
117                 int cur = u;
118                 while (cur != -1) {
119                     int pv = p[cur];
120                     int nv = (pv == -1 ? -1 : match[pv]);
121                     match[cur] = pv;
122                     if (pv != -1) match[pv] = cur;
123                     cur = nv;
124                 }
125                 ++matching;
126             }
127         }
128         return matching;
129     }
130 };
131 
132 int main() {
133     ios::sync_with_stdio(false);
134     cin.tie(nullptr);
135 
136     int n, m;
137     if (!(cin >> n >> m)) {
138         // Example fallback if no input provided
139         n = 5; m = 6;
140         Blossom bl(n);
141         vector<pair<int,int>> edges = {{0,1},{1,2},{2,0},{2,3},{3,4},{1,4}}; // triangle + tails
142         for (auto [u,v] : edges) bl.add_edge(u,v);
143         int sz = bl.solve();
144         cout << sz << "\n";
145         for (int i = 0; i < n; ++i) if (i < bl.match[i]) cout << i << " " << bl.match[i] << "\n";
146         return 0;
147     }
148 
149     Blossom bl(n);
150     for (int i = 0; i < m; ++i) {
151         int u, v; cin >> u >> v;
152         // assume 0-based input; if 1-based, uncomment next line
153         // --u; --v;
154         bl.add_edge(u, v);
155     }
156     int sz = bl.solve();
157     cout << sz << "\n";
158     for (int i = 0; i < n; ++i) if (i < bl.match[i]) cout << i << " " << bl.match[i] << "\n";
159     return 0;
160 }
161

This program implements Edmonds’ Blossom Algorithm for maximum cardinality matching in general graphs. It grows alternating trees with BFS, detects odd cycles via an LCA procedure, contracts blossoms by relabeling bases, and continues searching. Upon finding an augmenting path from a free root, it flips matched/unmatched edges along the path to increase the matching size by one. The main function reads a graph or uses an example, computes the maximum matching, prints its size, and then lists the matched pairs.

Time: O(V^3) (often written O(V^2 E) for sparse graphs)Space: O(V + E)

Blossom in action: triangle-with-tail example (hardcoded) demonstrating contraction necessity

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Blossom {
5     int n; vector<vector<int>> g; vector<int> match, p, base, q, lca_mark; vector<bool> used, blossom;
6     int lca_timer = 0;
7     Blossom(int n): n(n), g(n) {}
8     void add_edge(int u,int v){ if(u==v)return; g[u].push_back(v); g[v].push_back(u);}    
9     int lca(int a,int b){ ++lca_timer; while(true){ a=base[a]; lca_mark[a]=lca_timer; if(match[a]==-1) break; a=p[match[a]]; } while(true){ b=base[b]; if(lca_mark[b]==lca_timer) return b; if(match[b]==-1) break; b=p[match[b]]; } return -1; }
10     void markPath(int v,int b,int x){ while(base[v]!=b){ blossom[base[v]]=blossom[base[match[v]]]=true; p[v]=x; x=match[v]; v=p[match[v]]; }}
11     int findPath(int root){ used.assign(n,false); p.assign(n,-1); iota(base.begin(),base.end(),0); q.clear(); q.push_back(root); used[root]=true; for(size_t qi=0; qi<q.size(); ++qi){ int v=q[qi]; for(int u: g[v]){ if(base[v]==base[u]||match[v]==u) continue; if(u==root || (match[u]!=-1 && p[match[u]]!=-1)){ int cur_lca=lca(v,u); blossom.assign(n,false); markPath(v,cur_lca,u); markPath(u,cur_lca,v); for(int i=0;i<n;++i){ if(blossom[base[i]]){ base[i]=cur_lca; if(!used[i]){ used[i]=true; q.push_back(i);} } } } else if(p[u]==-1){ p[u]=v; if(match[u]==-1) return u; int w=match[u]; if(!used[w]){ used[w]=true; q.push_back(w);} } } } return -1; }
12     int solve(){ match.assign(n,-1); p.assign(n,-1); base.resize(n); used.assign(n,false); blossom.assign(n,false); lca_mark.assign(n,0); int ans=0; for(int v=0; v<n; ++v){ if(match[v]==-1){ int u=findPath(v); if(u==-1) continue; int cur=u; while(cur!=-1){ int pv=p[cur]; int nv=(pv==-1?-1:match[pv]); match[cur]=pv; if(pv!=-1) match[pv]=cur; cur=nv; } ++ans; } } return ans; }
13 };
14 
15 int main(){
16     ios::sync_with_stdio(false); cin.tie(nullptr);
17     // Graph: triangle (0-1-2-0) plus a tail 2-3 and a free vertex 4 connected to 1
18     // This setup forces the algorithm to detect and contract the triangle blossom to find the best matching.
19     int n = 5; Blossom bl(n);
20     vector<pair<int,int>> edges = {{0,1},{1,2},{2,0},{2,3},{1,4}};
21     for(auto [u,v]: edges) bl.add_edge(u,v);
22     int sz = bl.solve();
23     cout << "Maximum matching size: " << sz << "\nPairs:\n";
24     for(int i=0;i<n;++i) if(i < bl.match[i]) cout << i << " - " << bl.match[i] << "\n";
25     // Expected: size 2, e.g., (1,4) and (2,3), while vertex 0 remains unmatched.
26     return 0;
27 }
28

This standalone program builds a small non-bipartite graph with a triangle (a classic blossom) and shows that the algorithm contracts the triangle implicitly to find a maximum matching. It demonstrates why a simple bipartite-style augmenting path search would fail: the triangle’s odd cycle must be handled via contraction.

Time: O(V^3) on this input (but tiny constants for n=5)Space: O(V + E)

From maximum matching to minimum edge cover in a general graph (no isolated vertices)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Blossom {
5     int n; vector<vector<int>> g; vector<int> match, p, base, q, lca_mark; vector<bool> used, blossom;
6     int lca_timer = 0;
7     Blossom(int n): n(n), g(n) {}
8     void add_edge(int u,int v){ if(u==v) return; g[u].push_back(v); g[v].push_back(u);}    
9     int lca(int a,int b){ ++lca_timer; while(true){ a=base[a]; lca_mark[a]=lca_timer; if(match[a]==-1) break; a=p[match[a]]; } while(true){ b=base[b]; if(lca_mark[b]==lca_timer) return b; if(match[b]==-1) break; b=p[match[b]]; } return -1; }
10     void markPath(int v,int b,int x){ while(base[v]!=b){ blossom[base[v]]=blossom[base[match[v]]]=true; p[v]=x; x=match[v]; v=p[match[v]]; } }
11     int findPath(int root){ used.assign(n,false); p.assign(n,-1); iota(base.begin(), base.end(), 0); q.clear(); q.push_back(root); used[root]=true; for(size_t qi=0; qi<q.size(); ++qi){ int v=q[qi]; for(int u: g[v]){ if(base[v]==base[u] || match[v]==u) continue; if(u==root || (match[u]!=-1 && p[match[u]]!=-1)){ int cur_lca=lca(v,u); blossom.assign(n,false); markPath(v,cur_lca,u); markPath(u,cur_lca,v); for(int i=0;i<n;++i){ if(blossom[base[i]]){ base[i]=cur_lca; if(!used[i]){ used[i]=true; q.push_back(i);} } } } else if(p[u]==-1){ p[u]=v; if(match[u]==-1) return u; int w=match[u]; if(!used[w]){ used[w]=true; q.push_back(w);} } } } return -1; }
12     int solve(){ match.assign(n,-1); p.assign(n,-1); base.resize(n); used.assign(n,false); blossom.assign(n,false); lca_mark.assign(n,0); int ans=0; for(int v=0; v<n; ++v){ if(match[v]==-1){ int u=findPath(v); if(u==-1) continue; int cur=u; while(cur!=-1){ int pv=p[cur]; int nv=(pv==-1?-1:match[pv]); match[cur]=pv; if(pv!=-1) match[pv]=cur; cur=nv; } ++ans; } } return ans; }
13 };
14 
15 // Construct a minimum edge cover from a maximum matching.
16 // Precondition: the graph has no isolated vertices.
17 // Method: start with all matched edges in M. For each unmatched vertex v, pick any neighbor u and add (v,u).
18 
19 int main(){
20     ios::sync_with_stdio(false); cin.tie(nullptr);
21     int n, m; cin >> n >> m; 
22     Blossom bl(n);
23     vector<vector<int>> adj(n);
24     for(int i=0;i<m;++i){ int u,v; cin >> u >> v; // assume 0-based; if 1-based, decrement here
25         if(u==v) continue; // ignore self-loops for matching/edge cover
26         bl.add_edge(u,v); adj[u].push_back(v); adj[v].push_back(u);
27     }
28 
29     // Check for isolated vertices (no edge cover possible if any exist)
30     for(int v=0; v<n; ++v){ if(adj[v].empty()){ cout << "-1\n"; return 0; } }
31 
32     int msize = bl.solve();
33     // Build edge cover
34     vector<pair<int,int>> cover;
35     vector<bool> covered(n,false);
36 
37     // 1) Add all matched edges
38     for(int v=0; v<n; ++v){ if(bl.match[v] != -1 && v < bl.match[v]){
39             cover.emplace_back(v, bl.match[v]);
40             covered[v] = covered[bl.match[v]] = true;
41         }
42     }
43     // 2) For each uncovered vertex, add one arbitrary incident edge
44     for(int v=0; v<n; ++v){ if(!covered[v]){
45             int u = adj[v][0]; // there is at least one neighbor by precondition
46             cover.emplace_back(v, u);
47             covered[v] = covered[u] = true;
48         }
49     }
50 
51     // Output size and the edges of a minimum edge cover
52     // By theory, |cover| == n - msize
53     cout << cover.size() << "\n";
54     for(auto [u,v] : cover) cout << u << " " << v << "\n";
55     return 0;
56 }
57

This program first computes a maximum matching using Blossom, then constructs a minimum edge cover by adding all matched edges and, for each remaining uncovered vertex, adding any incident edge. The correctness follows from the formula |C_min| = |V| − |M_max| for graphs without isolated vertices. The program reports −1 if an isolated vertex exists (since an edge cover would then be impossible).

Time: O(V^3) for matching plus O(V + E) to build the coverSpace: O(V + E)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Edmonds' Blossom algorithm for maximum cardinality matching in general graphs.
5	// Complexity: O(V^3) in the classical implementation.
6	// Vertices are 0..n-1.
7
8	struct Blossom {
9	int n;
10	vector<vector<int>> g; // adjacency list
11	vector<int> match, p, base; // match[v], parent in alternating tree, base representative
12	vector<int> q; // BFS queue
13	vector<bool> used, blossom; // used in BFS, marks vertices in current blossom
14	vector<int> lca_mark; // time-stamped marks for LCA
15	int lca_timer = 0;
16
17	Blossom(int n): n(n), g(n) {}
18
19	void add_edge(int u, int v) {
20	if (u == v) return; // ignore self-loops
21	g[u].push_back(v);
22	g[v].push_back(u);
23	}
24
25	int lca(int a, int b) {
26	// Compute least common ancestor of a and b in alternating forest.
27	// We walk up through bases and matched/parent pointers.
28	++lca_timer;
29	// Mark ancestors of a
30	while (true) {
31	a = base[a];
32	lca_mark[a] = lca_timer; // mark base(a)
33	if (match[a] == -1) break; // reached root of this tree
34	a = p[match[a]]; // go to parent of matched partner
35	}
36	// Walk up from b until we hit a marked base
37	while (true) {
38	b = base[b];
39	if (lca_mark[b] == lca_timer) return b;
40	if (match[b] == -1) break;
41	b = p[match[b]];
42	}
43	return -1; // should not happen
44	}
45
46	void markPath(int v, int b, int x) {
47	// Mark all vertices on path v -> b in the alternating tree, setting blossom[]
48	// and redirecting parents so contraction can proceed.
49	while (base[v] != b) {
50	blossom[base[v]] = blossom[base[match[v]]] = true;
51	p[v] = x;
52	x = match[v];
53	v = p[match[v]];
54	}
55	}
56
57	int findPath(int root) {
58	used.assign(n, false);
59	p.assign(n, -1);
60	iota(base.begin(), base.end(), 0); // base[v] = v
61	q.clear(); q.reserve(n);
62	q.push_back(root);
63	used[root] = true;
64	for (size_t qi = 0; qi < q.size(); ++qi) {
65	int v = q[qi];
66	for (int u : g[v]) {
67	if (base[v] == base[u] \|\| match[v] == u) continue; // ignore trivial cases
68	if (u == root \|\| (match[u] != -1 && p[match[u]] != -1)) {
69	// Found a blossom with base cur_lca
70	int cur_lca = lca(v, u);
71	blossom.assign(n, false);
72	markPath(v, cur_lca, u);
73	markPath(u, cur_lca, v);
74	// Contract: set base[] to cur_lca for all in blossom, and enqueue new vertices
75	for (int i = 0; i < n; ++i) {
76	if (blossom[base[i]]) {
77	base[i] = cur_lca;
78	if (!used[i]) {
79	used[i] = true;
80	q.push_back(i);
81	}
82	}
83	}
84	} else if (p[u] == -1) {
85	// Expand alternating tree
86	p[u] = v;
87	if (match[u] == -1) {
88	// Found augmenting path ending at u
89	return u;
90	} else {
91	// Add the matched partner to the queue as an even-level vertex
92	int w = match[u];
93	if (!used[w]) {
94	used[w] = true;
95	q.push_back(w);
96	}
97	}
98	}
99	}
100	}
101	return -1; // no augmenting path from this root
102	}
103
104	int solve() {
105	match.assign(n, -1);
106	p.assign(n, -1);
107	base.resize(n);
108	used.assign(n, false);
109	blossom.assign(n, false);
110	lca_mark.assign(n, 0);
111	int matching = 0;
112	for (int v = 0; v < n; ++v) {
113	if (match[v] == -1) {
114	int u = findPath(v);
115	if (u == -1) continue; // no augmenting path from v
116	// Augment along v..u using p[] and match[]
117	int cur = u;
118	while (cur != -1) {
119	int pv = p[cur];
120	int nv = (pv == -1 ? -1 : match[pv]);
121	match[cur] = pv;
122	if (pv != -1) match[pv] = cur;
123	cur = nv;
124	}
125	++matching;
126	}
127	}
128	return matching;
129	}
130	};
131
132	int main() {
133	ios::sync_with_stdio(false);
134	cin.tie(nullptr);
135
136	int n, m;
137	if (!(cin >> n >> m)) {
138	// Example fallback if no input provided
139	n = 5; m = 6;
140	Blossom bl(n);
141	vector<pair<int,int>> edges = {{0,1},{1,2},{2,0},{2,3},{3,4},{1,4}}; // triangle + tails
142	for (auto [u,v] : edges) bl.add_edge(u,v);
143	int sz = bl.solve();
144	cout << sz << "\n";
145	for (int i = 0; i < n; ++i) if (i < bl.match[i]) cout << i << " " << bl.match[i] << "\n";
146	return 0;
147	}
148
149	Blossom bl(n);
150	for (int i = 0; i < m; ++i) {
151	int u, v; cin >> u >> v;
152	// assume 0-based input; if 1-based, uncomment next line
153	// --u; --v;
154	bl.add_edge(u, v);
155	}
156	int sz = bl.solve();
157	cout << sz << "\n";
158	for (int i = 0; i < n; ++i) if (i < bl.match[i]) cout << i << " " << bl.match[i] << "\n";
159	return 0;
160	}
161