1. 思想

矩阵树定理：对于一个无向图 $G$，它的生成树个数等于其基尔霍夫矩阵任何一个 $N - 1$ 阶主子式的行列式的绝对值。

• 度数矩阵 $D$：是一个 $N \times N$ 的矩阵，其中 $D[i][j]=0 (i \neq j)$，$D[i][i]=i$ 号点的度数。
• 邻接矩阵 $A$：是一个 $N \times N$ 的矩阵，其中 $A[i][i]=0$，$A[i][j]=A[j][i]=i,j$ 之间的边数。

然后 Kirchhoff（基尔霍夫）矩阵 $K = D-A$ 。

【注】行列式计算方法：将矩阵转为三角矩阵进行行列式计算。

2. 代码

/*************************************************************
                            矩阵树算法
时间复杂度：O(n^3)。
*************************************************************/

//浮点数运算版本（需高精度long double）
#include <bits/stdc++.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define re register
#define il inline
#define ll int
#define ld long double

const ld eps = 1e-10;
const ll MAXN = 100;

ll A[MAXN][MAXN];       //邻接矩阵
ll K[MAXN][MAXN];       //基尔霍夫矩阵

//快读
il ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

//计算矩阵行列式
il ld det(ll n)
{
    ld D[MAXN][MAXN];
    for(re ll i = 1; i <= n; ++i)
    {
        for(re ll j = 1; j <= n; ++j)
        {
            D[i][j] = K[i][j];
        }
    }
    //s计算交换行列次数，ans计算结果
    ll s = 0;
    ld ans = 1;
    for(re ll i = 1; i <= n; ++i)
    {
        //确保当前行首元素非零
        if(fabs(D[i][i]) < eps)
        {
            for(re ll j = i+1; j <= n; ++j)
            {
                if(fabs(D[j][i]) > eps)
                {
                    //利用库函数之间交换地址
                    std::swap(D[i],D[j]);
                    ++s;
                    break;
                }
                if(j == n)
                {
                    return 0;
                }
            }
        }
        //进行高斯消元
        for(re ll j = i+1; j <= n; ++j)
        {
            if(fabs(D[j][i]) > eps)             //行首元素非零
            {
                ld t = D[j][i]/D[i][i];
                for(re ll k = i; k <= n; ++k)
                {
                    D[j][k] -= D[i][k]*t;
                }
            }

        }
        ans *= D[i][i];
    }
    if(s & 1)   ans = -ans;
    return ans;
}


int main()
{
    ll n, m, k;
    while(scanf("%d%d%d", &n, &m, &k) == 3)
    {
        memset(K,0,sizeof(K));
        memset(A,0,sizeof(A));
        for(re ll j = 1; j <= m; ++j)
        {
            ll u,v;
            u = read();
            v = read();
            A[u][v] = A[v][u] = 1;
        }
        for(re ll j = 1; j <= n; ++j)
        {
            for(re ll d = 1; d <= n; ++d)
            {
                //构造基尔霍夫矩阵
                if(j != d && !A[j][d])
                {
                    ++K[j][j];
                    --K[j][d];
                }
            }
        }
        //【注意】long double型数据输出格式为%Lf
        printf("%.0Lf\n", det(n-1));
    }
    return 0;
}


/*
//整数运算版本
#include <bits/stdc++.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define re register
#define il inline
#define ll long long

//在快读基础上加上这两行
const ll MAXN = 1000;

ll A[MAXN][MAXN];       //邻接矩阵
ll K[MAXN][MAXN];       //基尔霍夫矩阵

//快读
il ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

//计算矩阵行列式
il ll det(ll n)
{
    //s计算交换行列次数，ans计算结果
    ll ans = 1;
    for(re ll i = 1; i <= n; ++i)
    {
        //确保当前行首元素非零
        if(!K[i][i])
        {
            for(re ll j = i+1; j <= n; ++j)
            {
                if(K[j][i])
                {
                    std::swap(K[i],K[j]);
                    ans = -ans;
                    break;
                }
                if(j == n)
                {
                    return 0;
                }
            }
        }
        //高斯消元
        for(re ll j = i+1; j <= n; ++j)
        {
            //避免了浮点运算
            while(K[j][i])
            {
                ll t = K[i][i]/K[j][i];
                for(re ll k = i; k <= n; ++k)
                {
                    K[i][k] -= t*K[j][k];
                }
                std::swap(K[i],K[j]);
                ans = -ans;
            }
        }
        ans *= K[i][i];
    }
    return ans;
}


int main()
{
    ll n, m, k;
    while(scanf("%lld%lld%lld", &n, &m, &k) == 3)
    {
        memset(K,0,sizeof(K));
        memset(A,0,sizeof(A));
        for(re ll j = 1; j <= m; ++j)
        {
            ll u,v;
            u = read();
            v = read();
            A[u][v] = A[v][u] = 1;
        }
        for(re ll j = 1; j <= n; ++j)
        {
            for(re ll d = 1; d <= n; ++d)
            {
                if(j != d && !A[j][d])
                {
                    ++K[j][j];
                    --K[j][d];
                }
            }
        }
        printf("%lld\n", det(n-1));
    }
    return 0;
}
*/