Description

【题目描述】
给出一个有 $n$ 个点 $m$ 条路径的无向连通图，判读其是否仙人掌图，且求出其支撑子图的个数。

支撑子图（spanning subgraph）：支撑子图也是原图的子图，这种子图可以比原来少一些边，但是不能破坏图的连通性，也不能去除原来图上的任何顶点。“支撑”的概念类似于我们熟知的“最小支撑树”，对于上例中的第一张图来说，任意去除回路I中的图或回路II中的一条边都能构成一个支撑子图，所以它的支撑子图一共有6 + 4 + 6 × 4 + 1 = 35种（注意图自身也是自己的一个子图）
【输入格式】
第一行两个整数 $n \ m$（$1 \le n \le 2×10^4$，$0 \le m \le 10^3$）。
下来 $m$ 行，每行表示一条路径。
每行：开始有一个整数 $k$（$2 \le k \le 10^3$），代表在这条路径上的顶点个数。下来是 $k$ 个 $1$ 到 $n$ 之间的整数，分别对应了一个顶点，相邻的顶点表示存在一条无向边。

【输出格式】
输出无向连通图的支撑子图的个数，如果它不是一张仙人掌图，输出0。注意最后的答案可能是一个很大很大的数。

【样例输入1】
14 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
2 2 14

【样例输出1】
35

【样例输入2】
10 2
7 1 2 3 4 5 6 1
6 3 7 8 9 10 2

【样例输出2】
0

【样例输入3】
5 1
4 1 2 3 4

【样例输出3】
0

Hint

scy不能过样例的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
struct node
{
int a[2100], len;
node(){memset(a,0,sizeof(a));len=1;}
}ans;
node operator (node no,int x)
{
for(int i=1;i<=no.len;i++)no.a[i]=x;
for(int i=1;i<=no.len;i++){no.a[i+1]+=no.a[i]/10000;no.a[i]%=10000;}
int i=no.len;
while(no.a[i+1]>0)
{
no.a[i+1]+=no.a[i]/10000;
no.a[i]%=10000;
i++;
}
no.len=i;
return no;
}
vector<int>G[N];
int tsp,dfn[N],low[N],dep[N];
bool flag;
void tarjan(int x,int xfa)
{
dfn[x]=low[x]=++tsp;
int num=0;
for(int y:G[x])if(y!=xfa)
{
if(!dfn[y])
{
dep[y]=dep[x]+1;
tarjan(y,x);
low[x]=min(low[x],low[y]);
}
else low[x]=min(low[x],dfn[y]);
if(dfn[x]>dfn[y])
{
num++;
ans=ans*(dep[x]-dep[y]+2);
}
}
if(num>1)flag=0;
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
while(m--)
{
int k,x,y;scanf("%d%d",&k,&x);k--;
while(k--)
{
scanf("%d",&y);
G[x].push_back(y);G[y].push_back(x);
x=y;
}
}
tsp=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
memset(dep,0,sizeof(dep));
ans.a[1]=1;flag=1;tarjan(1,0);
if(tsp!=n)flag=0;
if(!flag)printf("0");
else
{
printf("%d",ans.a[ans.len]);
for(int i=ans.len-1;i>=1;i--)printf("%04d",ans.a[i]);
}
printf("\n");
return 0;
}

</p>

hansang的正确代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
const int P = 10000;
struct hipr {
int len;
int a[3010];
hipr() {
memset(a, 0, sizeof(a));
len = 1;
}
} ans;
hipr operator*(hipr hp, int x) {
hipr res;
res.len = hp.len;
for (int i = 1; i &lt;= res.len; i++) {
	res.a[i] = hp.a[i] * x;
}
for (int i = 1; i &lt;= res.len; i++) {
	res.a[i + 1] += res.a[i] / P;
	res.a[i] %= P;
}

int i = res.len;
while (res.a[i + 1] &gt; 0) {
	i ++;
	res.a[i + 1] += res.a[i] / P;
	res.a[i] %= P;
}
res.len = i;

return res;

}
int k[N];
vector<int> G[N];
int tsp, dfn[N], low[N], dep[N];
bool flag;
void tarjan(int x, int xfa) {
dfn[x] = low[x] = ++tsp;
dep[x] = dep[xfa] + 1;
int sum = 0;
for (int y : G[x]) if (y != xfa) {
if (!dfn[y]) {
tarjan(y, x);
low[x] = min(low[x], low[y]);
		if (low[y] &lt; dfn[x]) {     //区别在这里，要让环上的每个点都知道有环
		// 可以自己模拟样例 2看看 
			sum ++;
		}
	}
	else {
		low[x] = min(low[x], dfn[y]);
	}
	
	if (dfn[x] &gt; dfn[y]) {
		sum ++;
		ans = ans * (dep[x] - dep[y] + 2); 
	}
}

if (sum &gt; 1) {
	flag = 0;
}

}
int main () {
ios::sync_with_stdio(False);
cin.tie(0);
int n, m;
cin &gt;&gt; n &gt;&gt; m;

for (int i = 1; i &lt;= m; i++) {
	cin &gt;&gt; k[i];
	
	int pre;
	cin &gt;&gt; pre;
	for (int j = 2; j &lt;= k[i]; j++) {
		int x;
		cin &gt;&gt; x;
		G[pre].push_back(x);
		G[x].push_back(pre);
		pre = x;
	}
}

tsp = 0; memset (dfn, 0, sizeof(dfn));
memset (low, 0, sizeof(low));
ans.len = 1;
ans.a[1] = 1;
dep[0] = 0;
flag = 1;

tarjan(1, 0);

if (tsp != n) {
	flag = 0;
}

if (!flag) {
	cout &lt;&lt; '0' &lt;&lt; "\n";
}
else {
	cout &lt;&lt; ans.a[ans.len];
	
	for (int i = ans.len - 1; i &gt;= 1; i--) {
		cout &lt;&lt; setw(4) &lt;&lt; setfill('0') &lt;&lt; ans.a[i];
	}
	cout &lt;&lt; "\n";
}

return 0;

}

</p>