儿子数大于1的树根或者 Low[v] >= DFN[u]的非树根节点v 就是割点。
#include <cstdio>
#include <cstring> const int N = ;
const int M = ;
struct Edge
{
int to,next;
bool cut;//是否为桥的标记
}edge[M];
int head[N],tot;
int Low[N],DFN[N],Stack[N];
int Index,top;
bool Instack[N];
bool cut[N];//是否为割点
int add_block[N];//删除一个点后增加的连通块
int bridge;
int va[N];
void addedge(int u,int v)
{
edge[tot].to = v;edge[tot].next =head[u];edge[tot].cut = false;
head[u] = tot++;
}
void Tarjan(int u,int pre)
{
int v;
Low[u] = DFN[u] = ++Index;
Stack[top++] = u;
Instack[u] = true;
int son = ;
for(int i = head[u];~i;i = edge[i].next)
{
v = edge[i].to;
if(v == pre)continue;
if( !DFN[v] )
{
son++;
Tarjan(v,u);
if(Low[u] > Low[v])Low[u] = Low[v];
//桥
if(Low[v] > DFN[u])
{
bridge++;
edge[i].cut = true;
edge[i^].cut = true;
}
if(u != pre && Low[v] >= DFN[u])//不是树根
{
cut[u] = true;
add_block[u]++;
}
}
else if( Low[u] > DFN[v])
Low[u] = DFN[v];
}
//树根，分支数大于1
if(u == pre && son > )cut[u] = true;
if(u == pre)add_block[u] = son - ;
Instack[u] = false;
top--;
}
void solve(){
memset(DFN,,sizeof DFN);
memset(Instack,,sizeof Instack);
memset(add_block,,sizeof add_block);
memset(cut,false,sizeof cut);
Index=top=;
int cnt=,ans=;
for(int i=;i<N;i++)
if(va[i]&&!DFN[i]){
Tarjan(i, i);
cnt++;
}
for(int i=;i<N;i++)
if(cut[i]){
ans++;
printf(" SPF node %d leaves %d subnets\n",i,cnt+add_block[i]);
}
if(ans==)
puts(" No SPF nodes"); }
void init(){
memset(head,-,sizeof head);
memset(va,,sizeof va);
tot=;
}
int main(){
int u,v,cas=;
init();
while(~scanf("%d",&u)){
if(u==&&tot){
printf("Network #%d\n",++cas);
solve();
init();
puts("");
continue;
}
scanf("%d",&v);
addedge(u,v);
addedge(v,u);
va[u]=va[v]=;
}
}