刚刚学习了什么是割点，桥，点双图，边双图，以及如何求，然后就想实践一下，结果悲剧了。。。
这道题的基本算法是用targin算法求出割点以及除去割点之后的联通块。
1.如果这个分支中只有1个割点，那么就需要建立一个特殊点。
2.如果有两个及以上的割点，就不需要去建立，因为无论哪个割点被爆了，都可以通过其他割点走到特殊点。
3.如果整张图没有割点，自己就是点双连通图，那就建立两个特殊点，防止被爆。
4.如果整张图就一个点，那么就建一个特殊点。
唔，这是多种情况吧，具体的话在程序注释里写。
#include<iostream> #include<cstdio> #include<cstring> #include<stack> using namespace std; struct h{ int to,next; }edge[10000]; int cnt,tot,m,p,t1,s1; int head[10000],dfn[10000],low[10000],node[10000]; long long ans1,ans2; void add(int u,int v) { edge[++cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; } void tarjan1(int x) { dfn[x]=low[x]=++tot; for (int i=head[x];i;i=edge[i].next) { if (dfn[edge[i].to]==0) { tarjan1(edge[i].to); low[x]=min(low[x],low[edge[i].to]); if (low[edge[i].to]>=dfn[x]) node[x]++; } else low[x]=min(low[x],dfn[edge[i].to]); } } stack<int>s; void tarjan2(int x)//第二次我们开始记录答案 { dfn[x]=low[x]=++tot; s.push(x); for (int i=head[x];i;i=edge[i].next) { if (dfn[edge[i].to]==0)//如果节点未被访问过 { tarjan2(edge[i].to);//继续搜 low[x]=min(low[x],low[edge[i].to]); if (low[edge[i].to]>=dfn[x])//如果这个点是一个割点 { int t=0,size=0,temp=0; while (t!=edge[i].to) //开始弹出我们现在枚举的这个联通块，这里不能写t!=x，y弹出后，栈顶不一定是x. { t=s.top(); s.pop(); if (node[t]>=2) temp++; //如果是割点的话，这个联通块的割点数加1 size++; //联通块大小加1 } if (node[x]>=2) temp++; size++; //下面就是四种情况分别记录答案 if (temp==1) { ans1++; ans2=ans2*(size-1); } else if (temp==0) { if (size==1) ans1++; else { ans1+=2; ans2=ans2*size*(size-1)/2; } } } } else low[x]=min(low[x],dfn[edge[i].to]); } } int main() { while (scanf("%d",&m),m>0) { tot=0; p++; cnt=0; memset(head,0,sizeof head); memset(dfn,0,sizeof dfn); memset(node,0,sizeof node); int n=0; ans1=0; ans2=1; for (int i=1;i<=m;i++) { scanf("%d%d",&s1,&t1); n=max(max(s1,t1),n); add(s1,t1);//链式前向星建边 add(t1,s1); } for (int i=1;i<=n;i++) if (dfn[i]==0) tarjan1(i); else node[i]++; //node记录这个点会存在于几个点双中，如果只存在于一个，就说明它不是割点，如果有两个及两个以上，那就是割点，这次tarjan用于判断割点 memset(dfn,0,sizeof dfn); for (int i=1;i<=n;i++) if (dfn[i]==0) tarjan2(i); printf("Case %d: %lld %lld ",p,ans1,ans2); } return 0; }
大概就是这样。