[spoj] HIGH - Highways (生成树计数)

时间:2022-12-15 15:41:12

传送门

输入格式:

第一行一个整数T,表示测试数据的个数 每个测试数据第一行给出 n,m 分别表示点数与边数 接下来 m 行,每行给出两个数 a,b ,表示 a,b 之间有一条无向边

输出格式:

每个测试数据,输出一个整数,表示给出的无向图的生成树的个数

输入输出样例

输入样例#1:

4

4 5

3 4

4 2

2 3

1 2

1 3

2 1

2 1

1 0

3 3

1 2

2 3

3 1

输出样例#1:

8

1

1

3

辗转相除

code:

//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define LL long long
#define M(a,b) memset(a,(b),sizeof(a))
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define C(i,a,b) for(register int i=(b);i>=(a);i--)
#define E(i,u) for(register int i=head[u];i;i=nxt[i])
using namespace std; LL rd() {
LL x=0,f=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f;c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*f;
} const int N=15;
int n,m;
LL mat[N][N]; LL det(LL da[N][N],int n) {
LL ans=1;
F(i,1,n) {
F(j,i+1,n) while(da[j][i]) {
LL t=da[i][i]/da[j][i];
F(k,i,n) da[i][k]=(da[i][k]-da[j][k]*t),swap(da[i][k],da[j][k]);
ans=-ans;
}
if(!da[i][i]) return 0;
ans*=da[i][i];
}
return abs(ans);
} int main() {
int T=rd();
while(T--) {
M(mat,0);
n=rd(),m=rd();
F(i,1,m) {
int a=rd(),b=rd();
mat[a][b]=mat[b][a]=-1;
mat[a][a]++,mat[b][b]++;
}
printf("%lld\n",det(mat,n));
}
return 0;
}