[poj1144]Network（求割点模板）

 1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<stack> 5 using namespace std; 6 #define N 1010 7 int n,m,ans,pd,son,cut[N],low[N],dfn[N]; 8 stack<int>s; 9 const int maxn=1e5+3;10 struct Edge{11 ????int nxt;12 ????int to;13 ????int w;14 }e[maxn];15 int head[maxn],cnt;16 void add_edge(int u,int v){17 ????e[cnt].to=v;18 ????e[cnt].nxt=head[u];19 ????head[u]=cnt++;20 }21 void tarjan(int u){22 ????low[u]=dfn[u]=++pd;23 ????for(int i=head[u];i!=-1;i=e[i].nxt){24 ????????int v=e[i].to;25 ????????if(!dfn[v]){26 ????????????tarjan(v);27 ????????????low[u]=min(low[u],low[v]);28 ????????????if(low[v]>=dfn[u]&&u!=1) cut[u]++;29 ????????????else if(u==1) son++;30 ????????}31 ????????else low[u]=min(low[u],dfn[v]);32 ????}33 }34 int main(){35 ????while(scanf("%d",&n)==1&&n){36 ????????int u,v;37 ????????memset(dfn,0,sizeof dfn);38 ????????memset(cut,0,sizeof cut);39 ????????memset(head,-1,sizeof head);40 ????????pd=ans=son=0;41 ????????while(scanf("%d",&u)==1&&u){42 ????????????while(getchar()!=‘\n‘){43 ????????????????scanf("%d",&v);44 ????????????????add_edge(u,v);45 ????????????????add_edge(v,u);46 ????????????}47 ????????}48 ????????tarjan(1);49 ????????for(int i=1;i<=n;i++) if(cut[i]) ans++;50 ????????if(son>1) ans++;51 ????????printf("%d\n",ans);52 ????}53 ????return 0;54 }