可看周冬的论文《生成树的计数及其应用》，利用Matrix-Tree定理解决生成树计数的问题，复杂度是矩阵乘法的复杂度O(n^3)。
总结：
无向图，允许有重边。
四个重要矩阵A(邻接矩阵),D(度数矩阵),C(KirchHoff矩阵，C=D-A),B(关联矩阵，B其实是用来证明和理解的)。
构造出C矩阵后，C的任何一个n-1阶主子式的行列式的绝对值就是答案。
ps:注意double矩阵求行列式的精度问题。
SPOJ104是论文里的例题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-8;
const double inf=1e10;
const int maxn=15;
int Sign(double x)
{
return x<-eps?-1:x>eps;
}
double Fabs(double x)
{
return (Sign(x)<0)?-x:(x>eps?x:0);
}
//*****************************Work*******************
int Cnt[maxn];
double C[maxn][maxn];
void Print(int n)
{
int i,j;
cout<<"*******************************************"<<endl;
for(i=0;i<n;++i)
{
for(j=0;j<n;++j)
{
cout<<" "<<C[i][j];
}
cout<<endl;
}
}
double Det(int n) //化成下三角形式
{
double ret=1.0,tmp;
int i,j,k,sign=0;
for(i=0;i<n;++i)
{
for(j=i;j<n;++j)
if(Sign(C[j][i])!=0)
break;
if(j==n)
return 0.0;
if(j!=i)
sign++;
for(k=0;k<n;++k)
swap(C[i][k],C[j][k]);
// Print(n);
for(j=i+1;j<n;++j)
{
tmp=C[i][j]/C[i][i];
for(k=i+1;k<n;++k)
{
C[k][j]-=tmp*C[k][i];
}
}
// Print(n);
}
for(i=0;i<n;++i)
ret*=C[i][i];
if(sign&1)
ret=-ret;
return ret;
}
int main()
{
int t,i,j,a,b,cnt,n,m;
scanf("%d",&t);
while(t--)
{
memset(Cnt,0,sizeof(Cnt));
memset(C,0,sizeof(C));
scanf("%d %d",&n,&m);
while(m--)
{
scanf("%d %d",&a,&b);
C[a-1][b-1]=C[b-1][a-1]=-1;
Cnt[a-1]++,Cnt[b-1]++;
}
for(i=0;i<n;++i)
C[i][i]=Cnt[i];
// Print(n);
printf("%.0lf\n",Det(n-1));
}
return 0;
}