传送门:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=251
解题思路:
这是一个简单的求割点的问题。
#include <iostream> #include <cstring> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; const int MAXN=110; const int MAXM=11000; struct Edge{ int to,next; }edge[MAXM]; int head[MAXN],tot; void addEdge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int LOW[MAXN],DFN[MAXN]; int cut[MAXN]; int Index; void Targan(int u,int pre){ DFN[u]=LOW[u]=++Index; int v; int son=0; for(int i=head[u];i!=-1;i=edge[i].next){ v=edge[i].to; if(!DFN[v]){ son++; Targan(v,u); if(LOW[u]>LOW[v]) LOW[u]=LOW[v]; if(u!=pre&&LOW[v]>=DFN[u]) cut[u]=true; }else if(LOW[u]>DFN[v]) LOW[u]=DFN[v]; } if(u==pre&&son>1) cut[u]=true; } void init(){ tot=0; memset(head,-1,sizeof(head)); } void solve(int N){ memset(DFN,0,sizeof(DFN)); memset(cut,false,sizeof(cut)); Index=0; for(int i=1;i<=N;i++) if(!DFN[i]) Targan(i,i); int ans=0; for(int i=1;i<=N;i++) if(cut[i]) ans++; printf("%d ",ans); } int main(){ int n; while(scanf("%d",&n)!=EOF&&n){ init(); int u; while(scanf("%d",&u)&&u){ char ch; while(ch=getchar()!=' '){ int v; scanf("%d",&v); addEdge(u,v); addEdge(v,u); } } solve(n); } }