题目链接：http://poj.org/problem?id=1523
题意：给出无向图的若干条边，求割点以及各个删掉其中一个割点后将图分为几块。
题目分析：割点用tarjan算法求出来，对于每个割点，dfs一次图，求出有几块不连通的子图。
AC代码：
#include<cstdio>
#include<cstring>
const int N=+;
struct EDGE{
int v,next;
}edge[N*N/];
int first[N],low[N],dfn[N],cut[N],vis[N];
int g,ans,rt,son,cnt,sum;
int min(int a,int b)
{
return a<b?a:b;
}
int max(int a,int b)
{
return a>b?a:b;
}
void AddEdge(int u,int v)
{
edge[g].v=v;
edge[g].next=first[u];
first[u]=g++;
}
void Tarjan(int u)
{
int i,v;
low[u]=dfn[u]=++cnt;
for(i=first[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
if(u==rt)
son++;
else
{
if(low[v]>=dfn[u])
cut[u]=true;
}
}
else
low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u)
{
vis[u]=;
for(int i=first[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(!vis[v])
dfs(v);
}
}
int main()
{
int t=,u,v,n,i,p;
while(scanf("%d",&u)&&u)
{
t++;
n=-;
memset(first,-,sizeof(first));
memset(cut,false,sizeof(cut));
memset(dfn,,sizeof(dfn));
g=cnt=sum=;
n=max(n,u);
scanf("%d",&v);
n=max(n,v);
AddEdge(u,v);
AddEdge(v,u);
while(scanf("%d",&u)&&u)
{
scanf("%d",&v);
n=max(n,u);
n=max(n,v);
AddEdge(u,v);
AddEdge(v,u);
}
for(i=;i<=n;i++)
{
if(!dfn[i])
{
rt=i;
son=;
Tarjan(i);
if(son>)
cut[rt]=true;
}
}
printf("Network #%d\n",t);
for(i=;i<=n;i++)
{
if(cut[i])
{
sum++;
ans=;
memset(vis,,sizeof(vis));
vis[i]=;
for(p=first[i];p!=-;p=edge[p].next)
{
v=edge[p].v;
if(!vis[v])
{
dfs(v);
ans++;
}
}
printf(" SPF node %d leaves %d subnets\n",i,ans);
}
}
if(sum==)
printf(" No SPF nodes\n");
printf("\n");
}
return ;
}