General Graph Maximum Matching Reconstruction

In a general graph, odd cycles prevent the direct use of bipartite matching algorithms. We use Edmonds' blossom algorithm.

For the current matching, run BFS to search for an augmenting path. When an edge between two vertices in the same BFS forest creates an odd cycle, contract the entire cycle into one blossom and continue the search in the contracted graph. Once an augmenting path is found, follow the parent pointers and flip the matched and unmatched edges along the path.

The implementation maintains the current mate of each vertex in $match$, the BFS parent in $p$, and the representative of the blossom containing each vertex in $base$. The least common ancestor of the two sides of a newly found blossom is obtained by alternately following matching edges and BFS-parent edges. During contraction, every representative on the odd cycle is replaced by that least common ancestor, and newly reachable vertices are inserted into the BFS queue.

One augmenting-path search takes $O(N^2)$ time, and the matching can be augmented at most $\lfloor N/2 \rfloor$ times. Therefore, the total time complexity is $O(N^3+M)$ and the memory complexity is .

For reconstruction, print each pair only once by selecting vertices $v$ such that $match[v]$ exists and $v<match[v]$.

Solution written by GPT5.6