UVA 315 ：Network （无向图求割顶）

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int N=109;struct Edge{ ???int to,next; ???Edge(){} ???Edge(int _to,int _next) ???{ ???????to=_to; ???????next=_next; ???}}edge[N*N*2];int head[N];int dfn[N],low[N];int iscut[N];int n,tot;int time_tag;void addedge(int u,int v){ ???edge[tot]=Edge(v,head[u]); ???head[u]=tot++;}void init(){ ???memset(dfn,0,sizeof(dfn)); ???memset(iscut,0,sizeof(iscut)); ???memset(head,-1,sizeof(head)); ???tot=time_tag=0;}void dfs(int u,int pre){ ???low[u]=dfn[u]=++time_tag; ???int child=0; ???//子节点数目 ????for(int i=head[u];~i;i=edge[i].next) ???{ ???????int v=edge[i].to; ???????if(!dfn[v]) ???// ???把dfn[]当vis[]使用 ????????{ ???????????child++; ???????????dfs(v,u); ???????????low[u]=min(low[u],low[v]); ???????????if(low[v]>=dfn[u]) ???????????????iscut[u]=1; ???????} ???????else if(dfn[v]<dfn[u] && v!=pre) ???????????low[u]=min(low[u],dfn[v]); ???} ???if(pre<0&&child==1) iscut[u]=0; ???//只有一个孩子的根节点 }int main(){ ???while(scanf("%d",&n)>0&&n) ???{ ???????init(); ???????int u,v; ???????while(scanf("%d",&u)>0&&u) ???????{ ???????????while(getchar()!=‘\n‘) ???????????{ ???????????????scanf("%d",&v); ???????????????addedge(u,v); ???????????????addedge(v,u); ???????????} ???????} ???????dfs(1,-1); ???????int ans=0; ???????for(int i=1;i<=n;i++) ???????????if(iscut[i]) ans++; ???????printf("%d\n",ans); ???}}