基本上是对着这篇博客写的。
定义一张图的一张图 \(G\) 的 Tutte 矩阵 \(\widetilde{A}(G)\) 为：
\[\widetilde{A}(G)_{i,j}=\begin{cases}0&((i,j)\notin E)\\x_{i,j}&((i,j)\in E \land i<j)\\-x_{i,j}&((i,j)\in E\land i>j)\end{cases} \]即如果 \(i,j\) 没边相连，那么 \(i\) 行 \(j\) 列和 \(j\) 行 \(i\) 列都是 \(0\)，否则 \(i\) 行 \(j\) 列上的值和 \(j\) 行 \(i\) 列上的值各自代表一个占位符，且两个占位符互为相反数。
定理 1：一张图有完美匹配当且仅当 \(\det \widetilde{A}(G)\ne 0\)。
考虑行列式的组合意义，相当于我钦定每条边有一个出边，连出若干个环，然后系数取决于逆序对与连边的 \(i>j\) 的次数之和的奇偶性。借鉴 LGV 引理的证明，我们利用行列式异号相消的性质，考虑如果存在一个长度为奇数的环，那么我们将这个环上所有边都反向，那么我们发现这样的操作对 \(p\) 的影响相当于是交换 \(\text{环长}-1\) 次 \(p\) 中的两个元素，而由于交换两个元素，逆序对奇偶性改变，且环长为奇数，所以逆序对个数不变，而环上每个 \(x_{i,j}\) 的符号改变，所以新的排列贡献是原排列贡献的相反数。也就是说如果存在奇环的排列的贡献之和为 \(0\)。这样如果行列式不是 \(0\)，说明必然存在一种用偶环分割这张图的方案。这时候我们在偶环上两两匹配即可。
维护多项式很困难，因此考虑将每个 \(x_{i,j}\) 随机赋权，然后计算行列式模一个大质数是否为 \(0\) 即可。
接下来考虑怎么求完美匹配的方案。很直观的想法是枚举每条边，然后尝试将其去掉，判断是否还存在完美匹配。这样复杂度 \(O(n^6)\)，显然不能要了。
考虑优化，容易发现 \(\widetilde{A}(G)\) 是斜对角矩阵，即 \(\forall i,j,\widetilde{A}(G)_{i,j}=-\widetilde{A}(G)_{j,i}\)，考虑发掘一些性质：
-
对于 \(n\) 是奇数，大小为 \(n\times n\) 的斜对角矩阵 \(A\)，\(\det A=0\)。因为 \(\det A=\det A^T=(-1)^n\det A\)，因此 \(\det A=0\)。
-
对于集合 \(I=\{i_1,i_2,\cdots,i_k\}\)，若 \(A\) 中第 \(i_1,i_2,\cdots,i_k\) 行线性无关，则由 \(A\) 的 \(I\) 中的行与 \(I\) 中的列组成的矩阵满秩。
这个定理同时证明了，一张图的最大匹配数为 \(\dfrac{1}{2}\text{rank}(\widetilde{A}(G))\)。
-
\(\text{rank}(A)\) 为偶数。由性质一可知。
先在考虑证明一些更强的性质：
定理 2：去掉 \(i,j\) 两个点以后，矩阵仍然存在完美匹配，当且仅当去掉 \(\widetilde{A}(G)\) 第 \(i\) 行第 \(j\) 列后，矩阵满秩。
显然前一个命题等价于去掉 \(i,j\) 两行和 \(i,j\) 两列后，矩阵的秩为 \(n-2\)。
充分性：因为去掉第 \(i\) 行 \(j\) 列后，矩阵秩为 \(n-1\)，所以去掉 \(i,j\) 两行和 \(i,j\) 两列后，矩阵秩不小于 \(n-3\)，而由于斜对角矩阵的秩为偶数，所以去掉 \(i,j\) 两行和 \(i,j\) 两列后，矩阵的秩为 \(n-2\)。
必要性：由于斜对角矩阵的秩为偶数，因此去掉第 \(i\) 行第 \(i\) 列以后，矩阵的秩应为 \(n-2\)。而去掉第 \(i\) 行第 \(i,j\) 两列后，矩阵的秩也为 \(n-2\) 可知，去掉第 \(i\) 行后第 \(j\) 列是其他列的线性组合。所以因为去掉第 \(i\) 行 \(j\) 列后，矩阵秩为 \(n-1\)。
定理 3：去掉 \(i,j\) 两个点以后，矩阵仍然存在完美匹配，当且仅当 \(\widetilde{A}(G)^{-1}_{i,j}\ne 0\)
矩阵的逆等于伴随矩阵除以矩阵的行列式，且 \(\det \widetilde{A}(G)\ne 0\)，因此容易由定理 2 推得定理 3。
这样我们可以求 \(n\) 次逆，复杂度 \(O(n^4)\)。继续优化。考虑去掉一行一列后怎么快速维护矩阵的逆的变化，这里引用下博客里的图。
这样去掉一行一列后，我们其实可以 \(O(n^2)\) 地算出去掉这一行一列后，对矩阵的逆的影响。这样总复杂度就可以做到 \(O(n^3)\)。
以上是存在完美匹配的情况，如果不存在完美匹配那情况其实也是类似的，你找出矩阵中最大的线性无关向量就可以规约到存在完美匹配的情况了。
代码实现起来不算太难。一个注意点是你去掉两个点的时候要 check 这两点间是否有边，因为 \(\widetilde{A}(G)^{-1}_{i,j}\ne 0\) 并没有保证 \(i,j\) 之间一定有边。
const int MAXN=1000;
const int MOD=1e9+7;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
mt19937 rng(time(0));
int n,m,k,a[MAXN+5][MAXN+5],b[MAXN+5][MAXN+5];
int tmp[MAXN+5][MAXN+5],c[MAXN+5][MAXN*2+5],d[MAXN+5][MAXN+5];
int res[MAXN+5],id[MAXN+5];
bool ins(int x){
for(int i=1;i<=n;i++)if(a[x][i]){
if(!b[i][i]){
for(int j=i;j<=n;j++)b[i][j]=a[x][j];
return 1;
}else{
int coef=MOD-1ll*qpow(b[i][i],MOD-2)*a[x][i]%MOD;
for(int j=i;j<=n;j++)a[x][j]=(a[x][j]+1ll*coef*b[i][j])%MOD;
}
}return 0;
}
bool vis[MAXN+5];
void del(int x,int y){
int iv=qpow(d[x][y],MOD-2);
for(int i=1;i<=k;i++)if(!vis[i])for(int j=1;j<=k;j++)if(!vis[j])
d[i][j]=(d[i][j]+1ll*(MOD-iv)*d[x][j]%MOD*d[i][y])%MOD;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);int w=rng()%(MOD-1)+1;
a[v][u]=w;a[u][v]=MOD-w;
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)tmp[i][j]=a[i][j];
vector<int>vec;
for(int i=1;i<=n;i++)if(ins(i))vec.pb(i);
printf("%d\n",vec.size()/2);
for(int i=0;i<vec.size();i++)id[vec[i]]=i+1;
k=vec.size();
for(int i=0;i<vec.size();i++)for(int j=0;j<vec.size();j++)
c[i+1][j+1]=tmp[vec[i]][vec[j]];
for(int i=1;i<=k;i++)c[i][i+k]=1;
for(int i=1;i<=k;i++){
int p=0;
for(int j=i;j<=k;j++)if(c[j][i])p=j;
for(int j=i;j<=k*2;j++)swap(c[i][j],c[p][j]);
int iv=qpow(c[i][i],MOD-2)%MOD;
for(int j=i;j<=k*2;j++)c[i][j]=1ll*c[i][j]*iv%MOD;
for(int j=i+1;j<=k;j++){
for(int t=i+1;t<=k*2;t++)c[j][t]=(c[j][t]+1ll*(MOD-c[j][i])*c[i][t])%MOD;
c[j][i]=0;
}
}
for(int i=k;i;i--){
for(int j=i+1;j<=k;j++)for(int t=k+1;t<=k*2;t++)
c[i][t]=(c[i][t]+1ll*(MOD-c[j][t])*c[i][j])%MOD;
}
for(int i=1;i<=k;i++)for(int j=1;j<=k;j++)d[i][j]=c[i][j+k];
for(int i=1;i<=k;i++){
if(vis[i])continue;
int u=i,v=0;
for(int j=i+1;j<=k;j++)
if(!vis[j]&&d[i][j]&&tmp[vec[i-1]][vec[j-1]]){
v=j;break;
}
res[vec[u-1]]=vec[v-1];res[vec[v-1]]=vec[u-1];
vis[u]=vis[v]=1;del(u,v);del(v,u);
}
for(int i=1;i<=n;i++)printf("%d%c",res[i]," \n"[i==n]);
return 0;
}