uva 315 Network

解法一：

找出所有的 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;
}