user
The Blossom Algorithm
:   The Blossom algorithm, developed by Jack Edmonds in 1965, is a seminal algorithm that solves the maximum matching problem for general graphs by extending the augmenting path concept to handle odd cycles.

Core Idea
:   Shrinking Blossoms
:   The key insight of the Blossom algorithm is to identify an odd cycle (a blossom) when encountered during the search for an augmenting path. When a blossom is detected, the algorithm *contracts* or *shrinks* the entire cycle into a single "pseudo-vertex". This creates a smaller, auxiliary graph.
:   The search for an augmenting path then continues in this contracted graph. If an augmenting path is found in the contracted graph that involves a pseudo-vertex (representing a shrunk blossom), this path can be "lifted" back to the original graph. The structure of the blossom allows the algorithm to find a corresponding augmenting path in the original graph that utilizes edges within the blossom.
:   This process of shrinking blossoms, searching for augmenting paths in the contracted graph, and expanding blossoms to find paths in the original graph is repeated until no more augmenting paths are found, at which point the current matching is maximum.

Problem
:   Maximum Matching in General Graphs
:   The problem addressed by the Blossom algorithm is finding a Maximum matching|maximum matching in a Graph (discrete mathematics)|general graph. Unlike Bipartite graph|bipartite graphs, general graphs can contain Cycle (graph theory)|odd-length cycles.

Graph and Matching Definition
:   A Graph (discrete mathematics)|graph **G** is formally defined by a set of Vertex (graph theory)|vertices **V** and a set of Edge (graph theory)|edges **E**, denoted as 

    G
    =
    (
    V
    ,
    E
    )
    {\displaystyle {\displaystyle G=(V,E)}}
    . An edge connects two vertices.
:   A Matching (graph theory)|matching **M** in **G** is a subset of the edges **E** such that no two edges in **M** share a common vertex. That is, for any two distinct edges 

    e

    1
    =


    u

    1
    ,

    v

    1
    ∈
    M
    {\displaystyle {\displaystyle e\_{1}={u\_{1},v\_{1}}\in M}}
     and 

    e

    2
    =


    u

    2
    ,

    v

    2
    ∈
    M
    {\displaystyle {\displaystyle e\_{2}={u\_{2},v\_{2}}\in M}}
    , the sets of vertices 

    u

    1
    ,

    v

    1
    {\displaystyle {\displaystyle {u\_{1},v\_{1}}}}
     and 

    u

    2
    ,

    v

    2
    {\displaystyle {\displaystyle {u\_{2},v\_{2}}}}
     are disjoint.

Maximum Matching
:   A Maximum matching|maximum matching is a matching **M** with the largest possible number of edges among all possible matchings in the graph **G**. The size of the matching is 

    |
    M

    |
    {\displaystyle {\displaystyle |M|}}
    .
:   The objective of the maximum matching problem is to find a matching **M** such that 

    |
    M

    |
    {\displaystyle {\displaystyle |M|}}
     is maximized.

Challenge in General Graphs
:   Odd Cycles
:   For Bipartite graph|bipartite graphs, efficient algorithms exist (e.g., Hopcroft-Karp algorithm) that rely on finding Augmenting path|augmenting paths. An augmenting path with respect to a matching **M** is a path that starts and ends at unmatched vertex|unmatched vertices, and its edges alternate between being outside **M** and inside **M**. If such a path exists, the matching can be increased by one edge by flipping the edges along the path (taking edges not in **M** and removing edges in **M** along the path). Berge's lemma states that a matching is maximum if and only if it has no augmenting path.
:   However, the presence of Cycle (graph theory)|odd-length cycles in general graphs complicates the search for augmenting paths. Standard Breadth-first search|BFS techniques used for bipartite graphs can get "confused" by odd cycles, which are sometimes called *blossoms* or *flowers* in this context. An odd cycle can contain an even number of matched edges and an odd number of unmatched edges with respect to an alternating path leading into it, potentially preventing the discovery of a true augmenting path using simple methods.

Objective
:   Given a general graph 

    G
    =
    (
    V
    ,
    E
    )
    {\displaystyle {\displaystyle G=(V,E)}}
    , the problem is to compute a matching 

    M
    ⊆
    E
    {\displaystyle {\displaystyle M\subseteq E}}
     such that its size 

    |
    M

    |
    {\displaystyle {\displaystyle |M|}}
     is maximum. The Blossom algorithm provides a polynomial-time solution to this problem.

Complexity
:   The original Blossom algorithm by Edmonds has a time complexity of 

    O
    (

    |
    V


    |

    2

    |
    E

    |
    )
    {\displaystyle {\displaystyle O(|V|^{2}|E|)}}
    . Subsequent improvements by Edmonds and others, including Robert Tarjan|Tarjan, led to more efficient versions. Modern implementations using advanced data structures achieve a time complexity of 

    O
    (

    |
    E

    |

    |
    V

    |
    )
    {\displaystyle {\displaystyle O(|E|{\sqrt {|V|}})}}
    , which is generally considered very efficient for this problem. An 

    O
    (

    |
    V


    |

    3
    )
    {\displaystyle {\displaystyle O(|V|^{3})}}
     variant is also commonly cited and easier to implement.
assistant
**Translation of**: Phix

**Translation of**: Python

```
# 20250512 Raku programming solution

# least common ancestor of x and y in the alternating forest
sub lca($x is copy, $y is copy, @bases, @matches, @paths, $n) {
   my @usedPath = False xx $n;
   loop {
      @usedPath[$x = @bases[$x]] = True;
      @matches[$x] < 0 ?? ( last ) !! $x = @paths[@matches[$x]]
   }
   loop {
      @usedPath[$y = @bases[$y]].Bool ?? ( last ) !! $y = @paths[@matches[$y]]     
   }
   return $y;
}

# mark path from v up to base0, setting parents to x
sub markPath($v is copy, $base0, $x is copy, @bases, @matches, @paths, @blossom) {
   while @bases[$v] != $base0 {
      my $mv = @matches[$v];
      @blossom[@bases[$mv]] = @blossom[@bases[$v]] = True;
      @paths[$v] = $x;
      $v = @paths[ $x = $mv ];
   }
}

# attempt to find an augmenting path from root
sub findPath(@adj, $root, $n, @matches is copy) {
   my @paths = -1 xx $n;
   my @bases = ^$n;
   my @queue = ($root);
   my (@used, @blossom) is default( False );
   @used[$root] = True;

   while my $v = @queue.shift {
      for @adj[$v].flat -> $u {
         next unless @bases[$v] != @bases[$u] && @matches[$v] != $u;
         if $u == $root || (@matches[$u] != -1 && @paths[@matches[$u]] != -1) {
            # Found a blossom; contract it
            my $curbase = lca($v, $u, @bases, @matches, @paths, $n);
            markPath($v, $curbase, $u, @bases, @matches, @paths, @blossom);
            markPath($u, $curbase, $v, @bases, @matches, @paths, @blossom);
            @queue.push: gather for ^$n -> $i {
               if @blossom[@bases[$i]] {
                  @bases[$i] = $curbase;
                  unless @used[$i] { @used[take $i] = True }
               }
            }
         } elsif @paths[$u] == -1 { # extend tree
            @paths[$u] = $v;
            if @matches[$u] == -1 { # augmenting path found
               my $v = $u;
               while $v != -1 {
                  my $prev = @paths[$v];
                  my $next = ( $prev != -1 ) ?? @matches[$prev] !! -1;
                  @matches[$v] = $prev;
                  @matches[$prev] = $v if $prev != -1;
                  $v = $next;
               }
               return (@matches, True);
            }
            @used[@matches[$u]] = True;
            @queue.push: @matches[$u];
         }
      }
   }
   return (@matches, False);
}

# find and return the matching array and the size of the matching
sub solve(@adj) {
   my @matches = -1 xx ( my $n = @adj.elems ); 
   my $res = 0;

   for ^$n -> $v {
      if @matches[$v] == -1 {
         my ($new_matches, $found) = findPath(@adj, $v, $n, @matches);
         if $found {
            @matches = @$new_matches;
            $res++;
         }
      }
   }
   return (@matches, $res);
}

# Example: 5-cycle (0–1–2–3–4–0)
my $n = 5;
my @edges = (0,1), (1,2), (2,3), (3,4), (4,0);
my @adj = [ [] xx $n ];
for @edges -> ($u, $v) {
   @adj[$u].push($v);
   @adj[$v].push($u);
}

my ($matches, $msize) = solve(@adj);
say "Maximum matching size: $msize";
say "Matched pairs:";
for $matches.kv -> $u, $v { say "  $u – $v" if $v != -1 && $u < $v }

```

You may Attempt This Online!