计数好题。
首先对于每个连通块独立考虑，最后合并答案。
发现 点数超过 1 的强连通分量一定删不掉。
- 若连通块中存在 点数超过 1 的强连通分量
- tarjan 缩点之后，称这些点数超过 1 的强连通分量为关键点；
- 那么两关键点之间的点也不能删；
- 于是对于剩下的点直接 dp 即可，由于可删的子树根一定是最后删的，无需考虑其他情况。
- 若连通块是一颗树
- 如果还是像刚才这样找个根 dp 一遍的话，有些方案算不进去（因为根有可能不是最后删除的）；
- 所以考虑对于每个点都作为根计算一遍答案，把所有的加在一起；
- 那么，对于一个删 \(k\) 个点的方案，就被计算了 \(s-k\) 次，\(s\) 为连通块大小，最后除掉即可。特别地，删 \(s\) 个点的方案没有算重。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e2+10,mod=1e9+9;
int n,m;
vector<int>A[N],B[N];
int top,dft,sct,dfn[N],low[N],scc[N],stk[N];
int cnt[N],C[N][N],inv[N];
void init(){
for(int i=0;i<=n;i++){
for(int j=C[i][0]=1;j<=i;j++){
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
}
inv[1]=1;
for(int i=2;i<=n;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
}
void tarjan(int u,int fa=0){
dfn[u]=low[u]=++dft,stk[++top]=u;
for(int v:A[u])if(v^fa){
if(!dfn[v])tarjan(v,u),low[u]=min(low[u],low[v]);
else if(!scc[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
sct++;
do scc[stk[top]]=sct;while(stk[top--]^u);
}
}
struct zj{
int n,a[N];
zj(int _n=0):n(_n){memset(a,0,sizeof a);}
zj operator * (const zj &x)const{
zj b(n+x.n);
for(int i=0;i<=n;i++)
for(int j=0;j<=x.n;j++)
b.a[i+j]=(b.a[i+j]+1ll*a[i]*x.a[j]%mod*C[i+j][i])%mod;
return b;
}
zj operator + (const zj &x)const{
zj b=x;
for(int i=0;i<=n;i++)
(b.a[i]+=a[i])%=mod;
return b;
}
}ans,f[N];
int rt,vis[N];
void cover(int u,int fa=0){
if(cnt[u]>1)rt=u;
vis[u]=1;
for(int v:B[u])if(v^fa)cover(v,u);
}
int tag[N];
vector<int>id;
bool push(int u,int fa=0){
int x=cnt[u]>1;
for(int v:B[u])if(v^fa)x|=push(v,u);
if(x)id.push_back(u);
return tag[u]=x;
}
void dfs2(int u,int fa=0){
f[u].a[0]=1;
for(int v:B[u])if(v^fa&&!tag[v]){
dfs2(v,u),f[u]=f[u]*f[v];
}
if(!tag[u]){
f[u].a[f[u].n+1]=f[u].a[f[u].n];
f[u].n++;
}
}
void solve1(int rt){
id.clear();
push(rt);
for(int u:id)dfs2(u),ans=ans*f[u];
}
void insert(int u,int fa=0){
id.push_back(u);
for(int v:B[u])if(v^fa)insert(v,u);
}
void solve(int u){
rt=0,cover(u);
if(rt)solve1(rt);
else{
id.clear();
insert(u);
zj sum(id.size());
for(int x:id){
dfs2(x);
sum=sum+f[x];
for(int y:id)f[y]=zj(0);
}
int len=id.size();
for(int i=0;i<len;i++)sum.a[i]=1ll*sum.a[i]*inv[len-i]%mod;
ans=ans*sum;
}
}
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&n,&m),init();
for(int u,v;m--;){
scanf("%d%d",&u,&v);
A[u].push_back(v),A[v].push_back(u);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int u=1;u<=n;u++)for(int v:A[u]){
if(scc[u]^scc[v]){
B[scc[u]].push_back(scc[v]);
}
}
for(int u=1;u<=n;u++)cnt[scc[u]]++;
ans.a[0]=1;
for(int i=1;i<=sct;i++)if(!vis[i])solve(i);
for(int i=0;i<=n;i++)printf("%d\n",ans.a[i]);
return 0;
}