http://acm.pku.edu.cn/JudgeOnline/problem?id=1144
Код:
#include<stdio.h> #include<memory.h> int ad[100][100]; int parent[100]; int num[100]; int visit[100]; int low[100]; int n,number,sum,cnt; void input(); void calCritical(); void dfs(int x); int main(){ char ch; while(scanf("%d",&n)==1&&n){ memset(ad,0,sizeof(ad)); input(); calCritical(); printf("%d\n",sum); } } void input(){ char ch; int tmp,i,j; while(scanf("%d",&number)==1&&number){ ch=getchar(); while(ch!='\n'){ scanf("%d",&tmp); ad[number][tmp]=ad[tmp][number]=1; ch=getchar(); } } } void calCritical(){ int i,j; sum=0;cnt=0; for(i=1;i<=n;i++) parent[i]=num[i]=low[i]=visit[i]=0; visit[1]=1; dfs(1); for(i=1,j=0;i<=n;i++){ if(ad[1][i]&&parent[i]==1) j++; } if(j>=2) sum++; } void dfs(int x){ int i,w,flag=0,count=0; num[x]=low[x]=++cnt; for(i=1;i<=n;i++){ w=i; if(ad[x][w]&&!visit[w]){ count++; visit[w]=1; parent[w]=x; dfs(w); if(low[w]>=num[x]&&x!=1) flag++; low[x]=(low[x]<=low[w]? low[x]:low[w]); } else if(ad[x][w]&&parent[x]!=w) low[x]=(low[x]<=num[w]? low[x]:num[w]); } if(flag) sum++; }