儿子数大于1的树根或者 Low[v] >= DFN[u]的非树根节点v 就是割点。
#include <cstdio> #include <cstring> const int N = 1001; const int M = 1000010; 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 = 0; 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^1].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 > 1)cut[u] = true; if(u == pre)add_block[u] = son - 1; Instack[u] = false; top--; } void solve(){ memset(DFN,0,sizeof DFN); memset(Instack,0,sizeof Instack); memset(add_block,0,sizeof add_block); memset(cut,false,sizeof cut); Index=top=0; int cnt=0,ans=0; for(int i=1;i<N;i++) if(va[i]&&!DFN[i]){ Tarjan(i, i); cnt++; } for(int i=1;i<N;i++) if(cut[i]){ ans++; printf(" SPF node %d leaves %d subnets ",i,cnt+add_block[i]); } if(ans==0) puts(" No SPF nodes"); } void init(){ memset(head,-1,sizeof head); memset(va,0,sizeof va); tot=0; } int main(){ int u,v,cas=0; init(); while(~scanf("%d",&u)){ if(u==0&&tot){ printf("Network #%d ",++cas); solve(); init(); puts(""); continue; } scanf("%d",&v); addedge(u,v); addedge(v,u); va[u]=va[v]=1; } }