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++;
}