【算法】点双连通分量
【题解】详见《算法竞赛入门竞赛入门经典训练指南》P318-319
细节在代码中用important标注。
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
using namespace std;
const int maxm=;
struct edge{int u,v,from;}e[maxm*];
int first[maxm],iscut[maxm],dfn[maxm],low[maxm],bccno[maxm],bcc_cnt,dfsnum,tot,n,m,kase;
vector<int>bcc[maxm];
stack<int>s;
void insert(int u,int v)
{tot++;e[tot].u=u;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
void tarjan(int x,int fa)
{
dfn[x]=low[x]=++dfsnum;
int child=;
for(int i=first[x];i;i=e[i].from)
if(e[i].v!=fa)
{
int y=e[i].v;
// s.push(i);
if(!dfn[y])
{
s.push(i);//
child++; //important
tarjan(y,x);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x])
{
iscut[x]=;
bcc_cnt++;
bcc[bcc_cnt].clear();
for(;;)
{
int now=s.top();s.pop();
int u=e[now].u,v=e[now].v;
if(bccno[u]!=bcc_cnt){bcc[bcc_cnt].push_back(u);bccno[u]=bcc_cnt;}
if(bccno[v]!=bcc_cnt){bcc[bcc_cnt].push_back(v);bccno[v]=bcc_cnt;}
// printf("%d\n",bcc_cnt);
if(u==x&&v==y)break;
}
}
}
else if(dfn[y]<dfn[x])s.push(i),low[x]=min(low[x],dfn[y]);//important
}
if(fa<&&child==)iscut[x]=;
}
int main()
{
scanf("%d",&m);
while(m!=)
{
memset(first,,sizeof(first));
n=;tot=;bcc_cnt=;
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
n=max(n,max(u,v));
insert(u,v);
insert(v,u);
}
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(iscut,,sizeof(iscut));
memset(bccno,,sizeof(bccno));
dfsnum=;
while(!s.empty())s.pop();
for(int i=;i<=n;i++)if(!dfn[i])tarjan(i,-);
long long ans1=,ans2=;
for(int i=;i<=bcc_cnt;i++)
{
int cut_cnt=;
for(int j=;j<bcc[i].size();j++)
if(iscut[bcc[i][j]])cut_cnt++;
if(cut_cnt==)
{
ans1++;
ans2*=(long long)(bcc[i].size()-cut_cnt);
}
}
if(bcc_cnt==)
{
ans1=;
ans2=bcc[].size()*(bcc[].size()-)/;
}
printf("Case %d: %lld %lld\n",++kase,ans1,ans2);
scanf("%d",&m);
}
return ;
}