解法一：
找出所有的 articulation points，把每一個點分別移除，用 DFS 走，確認是否除了被移除的點
外，剩下的所有點都可以走到，
若都可以走到，則此點不是 articulation point。
若有的走不到，則此點不是 articulation point。
注意：儲存的陣列要用 int，char 會不夠大。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int maps[101][101],pass[101]={0};
int places;
int counter;
void DFS(int point){
int i;
for(i=1;i<=maps[point][0];i++){
if(pass[maps[point][i]] != 1){
++counter;
pass[ maps[point][i] ] = 1;
DFS(maps[point][i]);
}
}
return;
}
int compute_points(int point){
int i;
counter=0;
memset(pass,0,sizeof(pass));
pass[point]=1;
for(i=1;i<=places;i++)
if(i!=point) break;
pass[i]=1;
++counter;
DFS(i);
return counter;
}
int main(void){
int p1,p2,i,points,critical;
char c;
while(scanf("%d",&places)!=EOF){
if(places==0) break;
memset(maps,0,sizeof(maps));
while(1){
scanf("%d",&p1);
if(p1==0) break;
c=1;
while(c!='\n'){
scanf("%d%c",&p2,&c);
maps[p1][ ++maps[p1][0] ]=p2;
maps[p2][ ++maps[p2][0] ]=p1;
}
}
critical=0;
for(i=1;i<=places;i++){
if(maps[i][0]==0) continue;
points=compute_points(i);
if( points!=(places-1) ) ++critical;
}
printf("%d\n",critical);
}
return 0;
}
--------------------------------------------------
解法二 (學習自：http://www.csie.ntnu.edu.tw/~u91029/Component.html#3)：
用一次 DFS 找出所有的 articulation point，
需要資訊：1. 此點可以到的最高 ancestor
2. 此點是第幾個走到的
判斷 articulation ：
如果被討論的 point 的其中一個 children，沒有辦法在此 point 被移除後，從被討論的 point 的
ancestor 走到，則此被討論的 point 為 articulation point。
因為為 articulation point 的條件是，此點被移除時，會使剩下的圖變成 disconnected graph，
所以 point 的任一 child 沒有和 point 的 ancestor 有相接時，此 point 為 articulation point。
計算所需的資訊：
DFS 時，存入走到此點是第幾個走到的，也是目前可以走到的最高 ancestor (自己)，
在走訪自己可以到的 children 時，
如果 child 已被走過，表示此 neighbor 為 ancestor，可以 update 自己可以走到的最高
ancestor。
如果 child 沒有被走過，則往下走。返回時，用此 child 的 "最高可以走到的 ancestor" update
自己可以走到的最高 ancestor，這是為了此點返回時，提供給 parent 的資訊。
然後判斷此點是否為 articuation point，看此 child 最高可以走到的 ancestor 是否是此 point 的
ancestor：
若否，則此點為 articulation point。
特別的判斷情況：root 沒有 parent，所以不能用上面的判斷標準。root 若有兩個以上的
children，則為 articulation point。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* pass : record the order point traveled */
/* low_back : record the highest ancestor point can reach */
int maps[101][101],pass[101],low_back[101];
int places;
int counter;
int t;
void DFS(int parent,int point){
int i;
int child=0,isCritical=0;
low_back[point]=pass[point]=++t;
for(i=1;i<=maps[point][0];i++){
if(maps[point][i] != parent){
/* point hasn't been traveled => tree edge */
if(pass[maps[point][i]] == 0){
child++;
DFS(point,maps[point][i]);
/* update ancestor the point can reach */
if(low_back[point] > low_back[maps[point][i]]){
low_back[point]=low_back[maps[point][i]];
}
/* if child cannot reach ancestor, */
/* then the point is critical */
if(low_back[maps[point][i]] >= pass[point]){
isCritical=1;
}
}else{
/* point has been traveled => back edge */
/* update ancestor the point can reach */
if(low_back[point] > pass[maps[point][i]]){
low_back[point]=pass[maps[point][i]];
}
}
}
}
if(parent==point && child <= 1)isCritical=0;
if(isCritical==1){
++counter;
}
return;
}
int compute_points(){
int i;
t=counter=0;
memset(pass,0,sizeof(pass));
memset(low_back,0,sizeof(low_back));
DFS(1,1);
return counter;
}
int main(void){
int p1,p2,i,points,critical;
char c;
while(scanf("%d",&places)!=EOF){
if(places==0) break;
memset(maps,0,sizeof(maps));
while(1){
scanf("%d",&p1);
if(p1==0) break;
c=1;
while(c!='\n'){
scanf("%d%c",&p2,&c);
maps[p1][ ++maps[p1][0] ]=p2;
maps[p2][ ++maps[p2][0] ]=p1;
}
}
critical=compute_points();
printf("%d\n",critical);
}
return 0;
}
