求割点，然后判断割点将图分为几部分
代码：
/* Low(u)=Min { DFS(u) DFS(v) (u,v)为后向边(返祖边) 等价于 DFS(v)<DFS(u)且v不为u的父亲节点 Low(v) (u,v)为树枝边(父子边) } 一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。 (2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)。 一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。*/ #include<iostream> using namespace std; const int MAX=1005; struct node { int v,next; }g[MAX*100]; int adj[MAX],cut[MAX],dfn[MAX],low[MAX],vis[MAX]; int n,m,ca,index,e; void add(int u,int v) { g[e].v=v; g[e].next=adj[u]; adj[u]=e++; g[e].v=u; g[e].next=adj[v]; adj[v]=e++; } void dfs(int u,int fa) { int son=0,v,i; dfn[u]=low[u]=++index; for(i=adj[u];i!=-1;i=g[i].next) { v=g[i].v; if(!dfn[v]) { son++; dfs(v,u); low[u]=min(low[u],low[v]); } else if(v!=fa) low[u]=min(low[u],dfn[v]); if((son>1&&fa==-1)||(fa!=-1&&low[u]>=dfn[v])) cut[u]=1; } } void ff(int u) { vis[u]=1; for(int i=adj[u];i!=-1;i=g[i].next) { if(!vis[g[i].v]) ff(g[i].v); } } void solve() { dfs(m,-1); printf("Network #%d/n",ca); int i,j,cnt,flag=1; for(i=m;i<=n;i++) { memset(vis,0,sizeof(vis)); vis[i]=1; cnt=0; for(j=m;j<=n;j++) { if(!vis[j]) { cnt++; ff(j); } } if(cnt>1)//割点 { flag=0; printf(" SPF node %d leaves %d subnets/n",i,cnt); } } if(flag) printf(" No SPF nodes/n"); printf("/n"); } int main() { int a,b; ca=0; while(true) { ca++; n=-1; m=1005; scanf("%d",&a); if(a==0) break; scanf("%d",&b); memset(dfn,0,sizeof(dfn)); memset(cut,0,sizeof(cut)); memset(adj,-1,sizeof(adj)); e=index=0; n=max(a,n); n=max(b,n); m=min(a,m); m=min(b,m); add(a,b); while(true) { scanf("%d",&a); if(a==0) { solve(); break; } else { scanf("%d",&b); n=max(a,n); n=max(b,n); m=min(a,m); m=min(b,m); add(a,b); } } } return 0; }
