Skip to content

Maximum Matching in General Graphs

Blossom algorithm

The blossom algorithm solves the maximum cardinality matching problem in general graphs. Jack Edmonds proposed it in 1961. With some modifications it also solves the maximum weight matching problem in general graphs. It was the first algorithm to prove that maximum matching can be solved in polynomial time.

Matching in a general graph differs from bipartite matching in that the graph may contain odd cycles.

general-matching-1

Take this graph as an example. If we simply flip the path (swap its matching and non-matching edges), the resulting \(M\) is not a valid matching: some vertices end up on two matching edges. The odd cycle is what causes the trouble.

Now consider how to augment in a general graph. We start as in the bipartite case. Take each unmatched vertex in turn, make it the root and label it "o", then label the vertices alternately "o" and "i". Every edge from an "i" vertex to an "o" vertex is a matching edge.

Let \(v\) be the current vertex and \(u\) one of its neighbors. There are two cases:

  1. \(u\) has not been visited. If it is unmatched, we have found an augmenting path; otherwise we go on searching from the mate of \(u\).
  2. \(u\) has been visited. If it is labeled "o", we have to contract a blossom; otherwise we have met an even cycle, and we skip it.

An even cycle is handled exactly as in a bipartite graph, so it can be ignored. After contracting the blossom, we continue to look for an augmenting path in the new graph.

general-matching-2

Let \(G\) be the original graph and \(G'\) the graph after contracting the blossom. We only need to prove two things:

  1. If \(G\) has an augmenting path, so does \(G'\).
  2. If \(G'\) has an augmenting path, so does \(G\).

general-matching-3

Let \((u,v)\) be the non-tree edge (the edge that closes the cycle), and define the base of the blossom as \(h=LCA(u,v)\). The odd cycle alternates everywhere except at \(h\), the only vertex whose two cycle edges have the same type: both are non-matching edges. So the tree edge that enters \(h\) must be a matching edge, and every edge that leaves the cycle from a vertex other than \(h\) is a non-matching edge.

There are two ways to leave the cycle through one of these outside edges: clockwise or counterclockwise.

general-matching-4

So contracting the blossom and not contracting it are equally correct.

In an implementation there is no need to actually contract a blossom once we find it: an array can record, for each vertex, the base of the blossom that contains it.

Complexity analysis

Each search for an augmenting path traverses all the edges and, whenever it meets a blossom, updates the vertices on that blossom: \(O(|E|^2)\).

Searching for an augmenting path from every unmatched vertex gives \(O(|V||E|^2)\) in total.

Reference code

Reference code
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
// graph
template <typename T>
class graph {
 public:
  struct edge {
    int from;
    int to;
    T cost;
  };

  vector<edge> edges;
  vector<vector<int>> g;
  int n;

  graph(int _n) : n(_n) { g.resize(n); }

  virtual int add(int from, int to, T cost) = 0;
};

// undirectedgraph
template <typename T>
class undirectedgraph : public graph<T> {
 public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;

  undirectedgraph(int _n) : graph<T>(_n) {}

  int add(int from, int to, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int)edges.size();
    g[from].push_back(id);
    g[to].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }
};

// blossom / find_max_unweighted_matching
template <typename T>
vector<int> find_max_unweighted_matching(const undirectedgraph<T> &g) {
  std::mt19937 rng(std::random_device{}());
  vector<int> match(g.n, -1);   // matching
  vector<int> aux(g.n, -1);     // timestamp
  vector<int> label(g.n);       // "o" or "i"
  vector<int> orig(g.n);        // base of the blossom
  vector<int> parent(g.n, -1);  // parent
  queue<int> q;
  int aux_time = -1;

  auto lca = [&](int v, int u) {
    aux_time++;
    while (true) {
      if (v != -1) {
        if (aux[v] == aux_time) {  // reached a visited vertex: it is the LCA
          return v;
        }
        aux[v] = aux_time;
        if (match[v] == -1) {
          v = -1;
        } else {
          v = orig[parent[match[v]]];  // continue from the parent of the mate
        }
      }
      swap(v, u);
    }
  };  // lca

  auto blossom = [&](int v, int u, int a) {
    while (orig[v] != a) {
      parent[v] = u;
      u = match[v];
      if (label[u] == 1) {  // relabel it "o", a starting point of the search
        label[u] = 0;
        q.push(u);
      }
      orig[v] = orig[u] = a;  // contract the blossom
      v = parent[u];
    }
  };  // blossom

  auto augment = [&](int v) {
    while (v != -1) {
      int pv = parent[v];
      int next_v = match[pv];
      match[v] = pv;
      match[pv] = v;
      v = next_v;
    }
  };  // augment

  auto bfs = [&](int root) {
    fill(label.begin(), label.end(), -1);
    iota(orig.begin(), orig.end(), 0);
    while (!q.empty()) {
      q.pop();
    }
    q.push(root);
    // label the starting vertex "o"; here 0 stands for "o" and 1 for "i"
    label[root] = 0;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int id : g.g[v]) {
        auto &e = g.edges[id];
        int u = e.from ^ e.to ^ v;
        if (label[u] == -1) {  // found an unvisited vertex
          label[u] = 1;        // label it "i"
          parent[u] = v;
          if (match[u] == -1) {  // found an unmatched vertex
            augment(u);          // trace the augmenting path
            return true;
          }
          // matched vertex: push its mate to extend the alternating tree
          label[match[u]] = 0;
          q.push(match[u]);
          continue;
        } else if (label[u] == 0 && orig[v] != orig[u]) {
          // found a visited vertex that is also labeled "o": a blossom
          int a = lca(orig[v], orig[u]);
          // find the LCA, then contract the blossom
          blossom(u, v, a);
          blossom(v, u, a);
        }
      }
    }
    return false;
  };  // bfs

  auto greedy = [&]() {
    vector<int> order(g.n);
    // shuffle order randomly
    iota(order.begin(), order.end(), 0);
    shuffle(order.begin(), order.end(), rng);

    // match every vertex that can be matched
    for (int i : order) {
      if (match[i] == -1) {
        for (auto id : g.g[i]) {
          auto &e = g.edges[id];
          int to = e.from ^ e.to ^ i;
          if (match[to] == -1) {
            match[i] = to;
            match[to] = i;
            break;
          }
        }
      }
    }
  };  // greedy

  // start with a random matching
  greedy();
  // look for an augmenting path from each unmatched vertex
  for (int i = 0; i < g.n; i++) {
    if (match[i] == -1) {
      bfs(i);
    }
  }
  return match;
}
UOJ #79. Maximum Matching in General Graphs
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <queue>
#include <random>
#include <vector>
using namespace std;

// graph
template <typename T>
class graph {
 public:
  struct edge {
    int from;
    int to;
    T cost;
  };

  vector<edge> edges;
  vector<vector<int>> g;
  int n;

  graph(int _n) : n(_n) { g.resize(n); }

  virtual int add(int from, int to, T cost) = 0;
};

// undirectedgraph
template <typename T>
class undirectedgraph : public graph<T> {
 public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;

  undirectedgraph(int _n) : graph<T>(_n) {}

  int add(int from, int to, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int)edges.size();
    g[from].push_back(id);
    g[to].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }
};

// blossom / find_max_unweighted_matching
template <typename T>
vector<int> find_max_unweighted_matching(const undirectedgraph<T> &g) {
  std::mt19937 rng(114514);  // the random seed does not matter here
  // you can also use chrono::steady_clock::now().time_since_epoch().count()
  // to get the current time
  vector<int> match(g.n, -1);   // matching
  vector<int> aux(g.n, -1);     // timestamp
  vector<int> label(g.n);       // "o" or "i"
  vector<int> orig(g.n);        // base of the blossom
  vector<int> parent(g.n, -1);  // parent
  queue<int> q;
  int aux_time = -1;

  auto lca = [&](int v, int u) {
    aux_time++;
    while (true) {
      if (v != -1) {
        if (aux[v] == aux_time) {  // reached a visited vertex: it is the LCA
          return v;
        }
        aux[v] = aux_time;
        if (match[v] == -1) {
          v = -1;
        } else {
          v = orig[parent[match[v]]];  // continue from the parent of the mate
        }
      }
      swap(v, u);
    }
  };  // lca

  auto blossom = [&](int v, int u, int a) {
    while (orig[v] != a) {
      parent[v] = u;
      u = match[v];
      if (label[u] == 1) {  // relabel it "o", a starting point of the search
        label[u] = 0;
        q.push(u);
      }
      orig[v] = orig[u] = a;  // contract the blossom
      v = parent[u];
    }
  };  // blossom

  auto augment = [&](int v) {
    while (v != -1) {
      int pv = parent[v];
      int next_v = match[pv];
      match[v] = pv;
      match[pv] = v;
      v = next_v;
    }
  };  // augment

  auto bfs = [&](int root) {
    fill(label.begin(), label.end(), -1);
    iota(orig.begin(), orig.end(), 0);
    while (!q.empty()) {
      q.pop();
    }
    q.push(root);
    // label the starting vertex "o"; here 0 stands for "o" and 1 for "i"
    label[root] = 0;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int id : g.g[v]) {
        auto &e = g.edges[id];
        int u = e.from ^ e.to ^ v;
        if (label[u] == -1) {  // found an unvisited vertex
          label[u] = 1;        // label it "i"
          parent[u] = v;
          if (match[u] == -1) {  // found an unmatched vertex
            augment(u);          // trace the augmenting path
            return true;
          }
          // matched vertex: push its mate to extend the alternating tree
          label[match[u]] = 0;
          q.push(match[u]);
          continue;
        } else if (label[u] == 0 && orig[v] != orig[u]) {
          // found a visited vertex that is also labeled "o": a blossom
          int a = lca(orig[v], orig[u]);
          // find the LCA, then contract the blossom
          blossom(u, v, a);
          blossom(v, u, a);
        }
      }
    }
    return false;
  };  // bfs

  auto greedy = [&]() {
    vector<int> order(g.n);
    // shuffle order randomly
    iota(order.begin(), order.end(), 0);
    shuffle(order.begin(), order.end(), rng);

    // match every vertex that can be matched
    for (int i : order) {
      if (match[i] == -1) {
        for (auto id : g.g[i]) {
          auto &e = g.edges[id];
          int to = e.from ^ e.to ^ i;
          if (match[to] == -1) {
            match[i] = to;
            match[to] = i;
            break;
          }
        }
      }
    }
  };  // greedy

  // start with a random matching
  greedy();
  // look for an augmenting path from each unmatched vertex
  for (int i = 0; i < g.n; i++) {
    if (match[i] == -1) {
      bfs(i);
    }
  }
  return match;
}

int main() {
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;

  undirectedgraph<int> g(n);

  while (m--) {
    int u, v;
    cin >> u >> v;
    g.add(u - 1, v - 1);  // 0-based
  }

  auto match = find_max_unweighted_matching(g);

  cout << count_if(match.begin(), match.end(), [](int x) { return x != -1; }) /
              2
       << endl;
  for (int i = 0; i < n; i++) cout << match[i] + 1 << " \n"[i == n - 1];

  return 0;
}

Matching in general graphs by Gaussian elimination

Hint

Before reading on, you may want to read the pages on matrices in the linear algebra section:

  • Matrices
  • Determinants
  • Gaussian elimination

This section presents a matching algorithm for general graphs that is based on Gaussian elimination. Compared with the classical blossom algorithm, it is easier to understand and to code, and it adapts well to problems such as finding the vertices that every maximum matching must cover. Its drawback is a large constant factor: Gaussian elimination really does use its full \(O(n^3)\), whereas the blossom algorithm rarely reaches its worst case.

Prerequisites: the Tutte matrix

Definition: For an undirected graph \(G = (V, E)\) with \(n\) vertices, the Tutte matrix \(\tilde{A}(G)\) is the \(n \times n\) matrix with entries

\[ \tilde{A}(G)_{i,j} = \begin{cases} x_{i,j}, & i<j,\; (v_i, v_j)\in E \\ -x_{i,j}, & i > j,\; (v_i, v_j) \in E \\ 0, & \text{otherwise} \end{cases} \]

Each \(x_{i, j}\) is a variable, so \(\tilde{A}(G)\) contains \(|E|\) variables in all.

Where no confusion can arise, we write \(\tilde{A}\) for \(\tilde{A}(G)\).

Theorem (Tutte's theorem): \(G\) has a perfect matching if and only if \(\det \tilde{A} \ne 0\).

Proof

We need the notion of an even cycle cover: an even cycle cover of an undirected graph \(G\) is a set of even cycles (2-cycles included) that covers every vertex exactly once.

It is easy to show that \(G\) has a perfect matching if and only if it has an even cycle cover.

  • If \(G\) has an even cycle cover, taking every other edge of each cycle gives a perfect matching.
  • If \(G\) has a perfect matching, the 2-cycles that correspond to its matching edges form an even cycle cover.

Next we prove that \(G\) has an even cycle cover if and only if \(\tilde{A} \ne 0\).

Consider the definition of the determinant

\[ \det A = \sum_{\pi} (-1)^{\pi} \prod_{i} A_{i, \pi_i} \]

where \(\pi\) ranges over all permutations, and \((-1)^{\pi}\) is \(-1\) if \(\pi\) has an odd number of inversions and \(1\) otherwise.

Every permutation can be viewed as a cycle cover of \(G\). If this cycle cover contains an odd cycle, its term and the term obtained by reversing that cycle sum to \(0\). So only even cycle covers can make the determinant different from \(0\), which completes the proof.

Theorem: \(\operatorname{rank}\tilde{A}\) is always even, and the size of a maximum matching of \(G\) is half of \(\operatorname{rank}\tilde{A}\).

Proof

The rank of a skew-symmetric matrix is always even. The second claim is left to the reader.

In practice we cannot compute with \(|E|\) variables. Instead we choose a number field, for example the residue system \(\mathcal{Z}_p\) of some prime \(p\), replace each variable by a random element of \(\mathcal{Z}_p\), and compute with those. For convenience, where no confusion can arise, \(\tilde{A}\) from now on denotes the matrix after this substitution.

Theorem: \(\operatorname{rank}\tilde{A}\) is at most twice the size of a maximum matching of \(G\), and the two are equal with probability at least \(1 - \frac n p\).

In maximum matching problems on general graphs \(n\) hardly ever exceeds \(10^3\), so in practice a prime \(p\) of the order of \(10^9\) is enough.

By this theorem, if you need only the size of a maximum matching and not the matching itself, a single Gaussian elimination that computes \(\operatorname{rank}\tilde{A}\) is enough, which is far simpler than the blossom algorithm. Reconstructing a solution is a little more complicated and needs the algorithm described below.

Constructing a perfect matching

By Tutte's theorem and the theorem above, if \(G\) has a perfect matching, then \(\tilde{A}\) has full rank with high probability. For convenience we leave out "with high probability" from here on.

Let \(v_i\) be the vertex of \(G\) numbered \(i\). The following theorem goes one step further:

Theorem: \(\tilde{A}^{-1}_{j,i} \ne 0 \iff G - \{v_i, v_j\}\) has a perfect matching.

Inverse and adjugate matrices

For any square matrix \(A\) of order \(n\), the adjugate matrix is defined by \(A^*_{i, j} = (-1)^{i + j} M_{j, i}\), where \(M_{j, i}\) is the minor obtained by deleting row \(j\) and column \(i\). In other words, if \(M\) is the cofactor matrix of \(A\), then \(A^* = M^T\).

Theorem: If \(A\) is invertible, then \(A^{-1} = \frac 1 {\det A} A^*\).

So here \(A^{-1}_{j, i} \ne 0 \iff M_{i, j} \ne 0\), that is, what is left of \(A\) after deleting row \(i\) and column \(j\) has full rank.

In other words, if \((v_i, v_j) \in E\) and \(\tilde{A}^{-1}_{j, i} \ne 0\), then some perfect matching contains the edge \((v_i, v_j)\). We call such an edge an allowed edge.

For an undirected graph \(G\) that has a perfect matching, this theorem gives a fairly obvious brute-force algorithm for finding one. Repeatedly enumerate \(i, j\); if \((v_i, v_j)\) is an allowed edge (the edge exists and \(\tilde{A}^{-1}_{j, i} \ne 0\)), add \((v_i, v_j)\) to the matching, delete both vertices from \(G\), and recompute \(\tilde{A}^{-1}\).

There are \(\frac n 2\) rounds of \(O(n^3)\) each, so the total is \(O(n ^ 4)\), which is rather slow. But we do not have to invert the matrix by Gaussian elimination every time we recompute \(\tilde{A}^{-1}\). We can use the following theorem instead:

Theorem (elimination theorem): Let

\[ A = \begin{bmatrix} a_{1, 1} & v^T \\ u & B \end{bmatrix} \quad A^{-1} = \begin{bmatrix} \hat a^{1, 1} & \hat v^T \\ \hat u & \hat B \end{bmatrix} \]

with \(\hat a_{1, 1} \ne 0\). Then

\[ B^{-1} = \hat B - \frac {\hat u \hat v^T} {\hat a_{1, 1}} \]

The theorem is stated for eliminating the first row and the first column, but it clearly generalizes to any row and any column. So we compute \(\tilde{A}^{-1}\) only once, at the start of the algorithm, and each time two vertices are deleted we run the \(O(n^2)\) elimination twice.

This is rather abstract; the C++ code may help
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void eliminate(int A[][MAXN], int r, int c) {  // eliminate row r and column c
  row_marked[r] = col_marked[c] = true;        // now eliminated

  int inv = quick_power(A[r][c], p - 2);  // modular inverse

  for (int i = 1; i <= n; i++)
    if (!row_marked[i] && A[i][c]) {
      int tmp = (long long)A[i][c] * inv % p;

      for (int j = 1; j <= n; j++)
        if (!col_marked[j] && A[r][j])
          A[i][j] = (A[i][j] - (long long)tmp * A[r][j]) % p;
    }
}

There are \(\frac n 2\) rounds of \(O(n^2)\) each, so the algorithm finds a perfect matching in \(O(n^3)\) time.

Constructing a maximum matching

We now know how to construct a perfect matching, but problems usually ask for a maximum matching.

As noted earlier, the size of a maximum matching of \(G\) is half of \(\operatorname{rank}\tilde{A}\). If we can find a largest full-rank square submatrix of \(\tilde{A}\), then a perfect matching of the induced subgraph that corresponds to it is a maximum matching of \(G\).

Look at it from another angle. If \(G\) has a perfect matching, then \(\tilde{A}\) has full rank; in other words, \(\tilde{A}\) is linearly independent. So when \(\tilde{A}\) does not have full rank, we can find a basis of \(\tilde{A}\) and keep only the rows and columns that correspond to it. This gives a largest full-rank square submatrix of \(\tilde{A}\).

Once we have this submatrix, the algorithm above finds a perfect matching of the induced subgraph, which is a maximum matching of the original graph. Gaussian elimination may swap rows, so take care to keep track of the vertex numbers in your implementation.

UOJ #79. Maximum Matching in General Graphs
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstring>
#include <iostream>
#include <random>
#include <utility>
using namespace std;

constexpr int MAXN = 505, p = (int)1e9 + 7;

int qpow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (long long)ans * a % p;
    a = (long long)a * a % p;
    b >>= 1;
  }
  return ans;
}

int A[MAXN][MAXN], B[MAXN][MAXN], t[MAXN][MAXN], id[MAXN];

// Gaussian elimination, O(n^3)
// if B is passed, compute the inverse; with nullptr, compute only the rank
void Gauss(int A[][MAXN], int B[][MAXN], int n) {
  if (B) {
    memset(B, 0, sizeof(t));
    for (int i = 1; i <= n; i++) B[i][i] = 1;
  }

  for (int i = 1; i <= n; i++) {
    if (!A[i][i]) {
      for (int j = i + 1; j <= n; j++)
        if (A[j][i]) {
          swap(id[i], id[j]);
          for (int k = i; k <= n; k++) swap(A[i][k], A[j][k]);

          if (B)
            for (int k = 1; k <= n; k++) swap(B[i][k], B[j][k]);
          break;
        }

      if (!A[i][i]) continue;
    }

    int inv = qpow(A[i][i], p - 2);

    for (int j = 1; j <= n; j++)
      if (i != j && A[j][i]) {
        int t = (long long)A[j][i] * inv % p;

        for (int k = i; k <= n; k++)
          if (A[i][k]) A[j][k] = (A[j][k] - (long long)t * A[i][k]) % p;

        if (B) {
          for (int k = 1; k <= n; k++)
            if (B[i][k]) B[j][k] = (B[j][k] - (long long)t * B[i][k]) % p;
        }
      }
  }

  if (B)
    for (int i = 1; i <= n; i++) {
      int inv = qpow(A[i][i], p - 2);

      for (int j = 1; j <= n; j++)
        if (B[i][j]) B[i][j] = (long long)B[i][j] * inv % p;
    }
}

bool row_marked[MAXN] = {false}, col_marked[MAXN] = {false};

int sub_n;  // size of the maximal full-rank submatrix

// eliminate one row and one column, O(n^2)
void eliminate(int r, int c) {
  row_marked[r] = col_marked[c] = true;  // now eliminated

  int inv = qpow(B[r][c], p - 2);

  for (int i = 1; i <= sub_n; i++)
    if (!row_marked[i] && B[i][c]) {
      int t = (long long)B[i][c] * inv % p;

      for (int j = 1; j <= sub_n; j++)
        if (!col_marked[j] && B[r][j])
          B[i][j] = (B[i][j] - (long long)t * B[r][j]) % p;
    }
}

int vertices[MAXN], girl[MAXN];  // girl: the mate, for the output

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  auto rng = mt19937(random_device{}());

  int n, m;
  cin >> n >> m;  // number of vertices and number of edges

  while (m--) {
    int x, y;
    cin >> x >> y;
    A[x][y] = rng() % p;
    A[y][x] = -A[x][y];  // Tutte matrix
  }

  for (int i = 1; i <= n; i++)
    id[i] = i;  // for the output: Gaussian elimination swaps columns
  memcpy(t, A, sizeof(t));

  Gauss(A, nullptr, n);

  for (int i = 1; i <= n; i++)
    if (A[id[i]][id[i]]) vertices[++sub_n] = i;  // find a maximal full-rank submatrix

  for (int i = 1; i <= sub_n; i++)
    for (int j = 1; j <= sub_n; j++) A[i][j] = t[vertices[i]][vertices[j]];

  Gauss(A, B, sub_n);

  for (int i = 1; i <= sub_n; i++)
    if (!girl[vertices[i]])
      for (int j = i + 1; j <= sub_n; j++)
        if (!girl[vertices[j]] && t[vertices[i]][vertices[j]] && B[j][i]) {
          // note the condition above: t is now a backup of the adjacency matrix,
          // and entry (j, i) of the inverse is nonzero iff this edge is allowed
          girl[vertices[i]] = vertices[j];
          girl[vertices[j]] = vertices[i];

          eliminate(i, j);
          eliminate(j, i);
          break;
        }

  cout << sub_n / 2 << '\n';
  for (int i = 1; i <= n; i++) cout << girl[i] << ' ';

  return 0;
}

Practice problems

References

  1. Mucha M, Sankowski P. Maximum matchings via Gaussian elimination
  2. Zixin Zhou, Jiaqi Yang. Matching in General Graphs Based on Linear Algebra (in Chinese)
  3. ZYQN, A Matching Algorithm for General Graphs Based on Linear Algebra (in Chinese)