网上的题解大都模糊，我可能写的也比较模糊吧，讲究看看。
大致题意：
原图没有一个割点时，特殊考虑，至少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 0x3f3f3f3ftypedef 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\n",++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;}LOJ-1308-Ant network(蚂蚁的网络)-求割点分隔开的子图个数及乘积
原文地址：https://www.cnblogs.com/zhazhaacmer/p/8497004.html