P4129 [NEERC 2005 / SHOI2006] 仙人掌 显然得到答案为 \prod_{i=1}^{sum} (num+1)，其中 sum 表示环的个数，num 表示环的边数。 注意需要使用高精度。 C++ #include using namespace std; const int N=1e5+5; #define int long long int n,m,cnt,idx; int dfn[N],low[N],tag[N],siz[N]; string ans="1"; vector g[N]; stack s; string cheng(string x,string y){ int a[70005],b[70005],c[70005],max1=x.size()+y.size(); string z=""; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(int i=x.size()-1,j=1;i>=0;i--,j++) a[j]=x[i]-'0'; for(int i=y.size()-1,j=1;i>=0;i--,j++) b[j]=y[i]-'0'; for(int i=1;i=1;i--) z+=c[i]+'0'; return z; } void tarjan(int u,int fa){ dfn[u]=low[u]=++idx; s.push(u); for(int v:g[u]){ if(v==fa) continue; if(!dfn[v]){ tarjan(v,u); if(low[v]dfn[u]) s.pop(); else{ siz[++cnt]=1; while(1){ int y=s.top(); s.pop(); siz[cnt]++; if(y==v) break; } } } else if(low[v]>n>>m; for(int i=1,k,u,v;i>k>>u; for(int j=1;j>v; g[u].push_back(v); g[v].push_back(u); u=v; } } tarjan(1,0); int flag=1; for(int i=1;i=2){ flag=0; break; } } if(flag){ for(int i=1;i `#include using namespace std; const int N=1e5+5; #define int long long int n,m,cnt,idx; int dfn[N],low[N],tag[N],siz[N]; string ans="1"; vectorint> g[N]; stackint> s; string cheng(string x,string y){ int a[70005],b[70005],c[70005],max1=x.size()+y.size(); string z=""; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(int i=x.size()-1,j=1;i>=0;i--,j++) a[j]=x[i]-'0'; for(int i=y.size()-1,j=1;i>=0;i--,j++) b[j]=y[i]-'0'; for(int i=1;ix.size();i++) for(int j=1;jy.size();j++) c[i+j-1]+=a[i]*b[j]; for(int i=1;imax1;i++) { c[i+1]+=c[i]/10; c[i]%=10; } while(!c[max1]) max1--; for(int i=max(1ll,max1);i>=1;i--) z+=c[i]+'0'; return z; } void tarjan(int u,int fa){ dfn[u]=low[u]=++idx; s.push(u); for(int v:g[u]){ if(v==fa) continue; if(!dfn[v]){ tarjan(v,u); if(low[v]dfn[u]){ low[u]=min(low[u],low[v]); tag[u]++; } else if(low[v]>dfn[u]) s.pop(); else{ siz[++cnt]=1; while(1){ int y=s.top(); s.pop(); siz[cnt]++; if(y==v) break; } } } else if(low[v]dfn[u]){ low[u]=min(low[u],dfn[v]); tag[u]++; } } } signed main(){ cin>>n>>m; for(int i=1,k,u,v;im;i++){ cin>>k>>u; for(int j=1;jk;j++){ cin>>v; g[u].push_back(v); g[v].push_back(u); u=v; } } tarjan(1,0); int flag=1; for(int i=1;in;i++){ if(!dfn[i]||tag[i]>=2){ flag=0; break; } } if(flag){ for(int i=1;icnt;i++) ans=cheng(ans,to_string(siz[i]+1)); coutans; } else cout"0"; return 0; }`
仙人掌图
笔记