Matrix-Tree 定理(基尔霍夫矩阵树定理)求图生成树个数

发布于 2020-08-12  0 次阅读


作用:

Matrix-Tree 定理作用:给定 n 个点 m 条边的无向图,求图的生成树个数。

结论:

对于已经得出的基尔霍夫矩阵,去掉其随意一行一列得出的矩阵的行列式,其绝对值为生成树的个数

Code:

其中mat为基尔霍夫矩阵,n为点的个数。(for循环也可写作2~n)

ll gauss(int n, ll mat[][N]){//求矩阵K的n-1阶顺序主子式
    ll res=1;
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n-1;j++){
            while(mat[j][i]){
                int t=mat[i][i]/mat[j][i];
                for(int k=i;k<=n-1;k++)
                    mat[i][k]=(mat[i][k]-t*mat[j][k]+mod)%mod;
                swap(mat[i],mat[j]);
                res=-res;
            }
        }
        res=(res*mat[i][i])%mod;
    }
    return (res+mod)%mod;
}

平平无奇的大学在读本科生