生成樹計數-Matrix-Tree定理

/*
 *算法引入：
 *給定一個無向圖G，求它生成樹的個數t(G);
 *
 *算法思想：
 *(1)G的度數矩陣D[G]是一個n*n的矩陣,并且滿足:當i≠j時,dij=0;當i=j時,dij等于vi的度數;
 *(2)G的鄰接矩陣A[G]是一個n*n的矩陣,并且滿足:如果vi,vj之間有邊直接相連,則aij=1,否則為0;
 *定義圖G的Kirchhoff矩陣C[G]為C[G]=D[G]-A[G];
 *Matrix-Tree定理:G的所有不同的生成樹的個數等于其Kirchhoff矩陣C[G]任何一個n-1階主子式的行列式的絕對值；
 *所謂n-1階主子式,就是對于r(1≤r≤n),将C[G]的第r行,第r列同時去掉後得到的新矩陣,用Cr[G]表示;
 *
 *Kirchhoff矩陣的特殊性質：
 *(1)對于任何一個圖G,它的Kirchhoff矩陣C的行列式總是0,這是因為C每行每列所有元素的和均為0;
 *(2)如果G是不連通的,則它的Kirchhoff矩陣C的任一個主子式的行列式均為0;
 *(3)如果G是一顆樹,那麼它的Kirchhoff矩陣C的任一個n-1階主子式的行列式均為1;
 *
 *算法舉例：
 *SPOJ104(Highways)
 *
 *題目位址：
 *http://www.spoj.com/problems/HIGH/
 *
 *題目大意：
 *一個有n座城市的組成國家,城市1至n編号,其中一些城市之間可以修建高速公路;
 *需要有選擇的修建一些高速公路,進而組成一個交通網絡;
 *計算有多少種方案,使得任意兩座城市之間恰好隻有一條路徑;
**/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=15;

typedef long long LL;

int degree[N];
LL C[N][N];

LL det(LL a[][N],int n)//生成樹計數:Matrix-Tree定理
{
    LL ret=1;
    for(int i=1; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
            while(a[j][i])
            {
                LL t=a[i][i]/a[j][i];
                for(int k=i; k<n; k++)
                    a[i][k]=(a[i][k]-a[j][k]*t);
                for(int k=i; k<n; k++)
                    swap(a[i][k],a[j][k]);
                ret=-ret;
            }
        if(a[i][i]==0)
            return 0;
        ret=ret*a[i][i];
    }
    if(ret<0)
        ret=-ret;
    return ret;
}

int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
    int tcase;
    scanf("%d",&tcase);
    while(tcase--)
    {
        memset(degree,0,sizeof(degree));
        memset(C,0,sizeof(C));
        int n,m;
        scanf("%d%d",&n,&m);
        int u,v;
        while(m--)
        {
            scanf("%d%d",&u,&v);
            u--;
            v--;
            C[u][v]=C[v][u]=-1;
            degree[u]++;
            degree[v]++;
        }
        for(int i=0; i<n; ++i)
            C[i][i]=degree[i];
        printf("%lld\n",det(C,n));
    }
    return 0;
}