网上的题解大都模糊，我可能写的也比较模糊吧，讲究看看。
大致题意：
原图没有一个割点时，特殊考虑，至少ans1=2个通风井，方案数n*(n-1)/2;
原图上有多个割点时，每个（由割点限制成几部分的）联通块个数即为ans1；需要dfs进行vis标记和iscut区分，不重不漏；
ans2，建设时避开在割点上建设通风井（通风井数量可最小化，以免通风井损毁后还需再建一个以备万一）；求解时：当一个颜色块有两个割点时，摧毁一个蚂蚁们总可以通过另一个割点紧急转移；当一个颜色块有仅一个割点时，摧毁割点后就必须在颜色块内部建设一个。
//五点双环一割点，（发现这个样例：颜色块为1割点不为1，用颜色块来计算就不对头了！）
12
5 6 0 1 1 2 0 2 2 3 2 4 3 4
AC题解：
//头文件都私奔了！ #include<set> using namespace std; #define N 10100 #define inf 0x3f3f3f3f typedef unsigned long long ULL; int n,m,Time; //单指向边的共m条; vector<int>G[N]; ///一次存贮1个内存！！ int dfn[N],low[N]; int color_num,in[N]; stack<int>st; int father[N]; int cas; int color[N]; ///表示i在的颜色块的编号，本题无用！ bool iscut[N]; ///表示i 是否为割点 bool vis[N]; ///dfs中有用 int test_num; ///dfs中从某u点(非割点)出发可以遇见的 set<int>ss; ///从某u点(非割点)出发dfs中的遇见割点(方便去重用set） ULL mod;///模数 void init() { for(int i=0;i<=n;i++){ G[i].clear(); } memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); Time=0; color_num=0; memset(in,0,sizeof(in));memset(color,0,sizeof(color)); memset(iscut,false,sizeof(iscut)); memset(father,-1,sizeof(father)); while(!st.empty())st.pop(); } void tarjan(int u,int fa) { dfn[u]=low[u]=++Time; st.push(u);in[u]=1; father[u]=fa; ///别忘记！ for(int i=0;i<(int)G[u].size();i++){ int v=G[u][i]; if(!dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]); } else if(v!=fa&&in[u]==1){ ///子节点在队列中并且不是父节点 low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ ++color_num; int top; do{ top=st.top();st.pop(); in[top]=0; color[top]=color_num; //细节！ }while(top!=u); } } ULL fact_mod(ULL x){ ///对2的64次方取模(mod只有一半) while(x/(ULL)2>=mod) x=x-mod-mod; return x; } void dfs(int u) { vis[u]=1; test_num++; ///从u点出发的由割点分隔开的联通图中的非割点数目 for(int i=0;i<(int)G[u].size();i++){ int v=G[u][i]; if(iscut[v]){ ss.insert(v);continue; } if(iscut[v]||vis[v])continue; ///vis防重复，iscut防dfs到切点 dfs(v); } } void solve() //缩点 { tarjan(0,-1); ///单源点图，求DAG int ans1=0; ULL ans2=1; int rootsons=0,u,cnt=0; ///cnt表示割点个数 for(int i=0;i<n;i++){ ///求割点，分类特判源点0是否为割点 if(father[i]==0) rootsons++; else{ u=father[i]; ///父节点 if(dfn[u]<=low[i]&&iscut[u]==false){ iscut[u]=true;cnt++; } } } if(rootsons>1){ ///特判源点 iscut[0]=true;cnt++; } if(cnt==0){ ///没有割点的图 ans1=2; ans2=(ULL)n*(n-1)/2; ans2=fact_mod(ans2); } else{ memset(vis,false,sizeof(vis)); for(int i=0;i<n;i++){ ///多个割点的图 if(iscut[i]||vis[i]) continue; ss.clear();test_num=0; dfs(i); if(ss.size()<=1){ ans1++;ans2=ans2*(ULL)test_num; } } } ans2=fact_mod(ans2); printf("Case %d: %d %llu ",++cas,ans1,ans2); } int main() { int T; scanf("%d",&T); cas=0; mod=(ULL)1; ///求模数 for(int i=1;i<=63;i++){ mod=mod*(ULL)2; } while(T--){ scanf("%d%d",&n,&m); init(); int x,y; for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); } solve(); } return 0; }