1 files changed, 23 insertions, 0 deletions
diff --git a/content/graph/matching.cpp b/content/graph/matching.cpp
new file mode 100644
index 0000000..dcaea8c
--- /dev/null
+++ b/content/graph/matching.cpp
@@ -0,0 +1,23 @@
+constexpr int MOD=1'000'000'007, I=10;
+vector<vector<ll>> adj, mat;
+
+int max_matching() {
+	int ans = 0;
+	mat.assign(sz(adj), {});
+	for (int _ = 0; _ < I; _++) {
+		for (int v = 0; v < sz(adj); v++) {
+			mat[v].assign(sz(adj), 0);
+			for (int u : adj[v]) {
+				if (u < v) {
+					mat[v][u] = rand() % (MOD - 1) + 1;
+					mat[u][v] = MOD - mat[v][u];
+		}}}
+		gauss(sz(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@
+		int rank = 0;
+		for (auto& row : mat) {
+			if (*max_element(all(row)) != 0) rank++;
+		}
+		ans = max(ans, rank / 2);
+	}
+	return ans;
+}