/* algo7-3.c 實(shí)現(xiàn)算法7.10、7.11的程序 */
 #include"c1.h"
 #define MAX_NAME 2 /* 頂點(diǎn)字符串的最大長(zhǎng)度+1 */
 typedef int InfoType;
 typedef char VertexType[MAX_NAME]; /* 字符串類型 */
 #include"c7-2.h"
 #include"bo7-2.c"

 int count; /* 全局量count對(duì)訪問計(jì)數(shù) */
 int low[MAX_VERTEX_NUM];

 void DFSArticul(ALGraph G,int v0)
 { /* 從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，查找并輸出關(guān)節(jié)點(diǎn)。算法7.11 */
   int min,w;
   ArcNode *p;
   visited[v0]=min=++count; /* v0是第count個(gè)訪問的頂點(diǎn) */
   for(p=G.vertices[v0].firstarc;p;p=p->nextarc) /* 對(duì)v0的每個(gè)鄰接頂點(diǎn)檢查 */
   {
     w=p->adjvex; /* w為v0的鄰接頂點(diǎn) */
     if(visited[w]==0) /* w未曾訪問，是v0的孩子 */
     {
       DFSArticul(G,w); /* 返回前求得low[w] */
       if(low[w]<min)
         min=low[w];
       if(low[w]>=visited[v0])
         printf("%d %s\n",v0,G.vertices[v0].data); /* 關(guān)節(jié)點(diǎn) */
     }
     else if(visited[w]<min)
       min=visited[w]; /* w已訪問，w是v0在生成樹上的祖先 */
   }
   low[v0]=min;
 }

 void FindArticul(ALGraph G)
 { /* 連通圖G以鄰接表作存儲(chǔ)結(jié)構(gòu)，查找并輸出G上全部關(guān)節(jié)點(diǎn)。算法7.10 */
   /* 全局量count對(duì)訪問計(jì)數(shù)。 */
   int i,v;
   ArcNode *p;
   count=1;
   low[0]=visited[0]=1; /* 設(shè)定鄰接表上0號(hào)頂點(diǎn)為生成樹的根 */
   for(i=1;i<G.vexnum;++i)
     visited[i]=0; /* 其余頂點(diǎn)尚未訪問 */
   p=G.vertices[0].firstarc;
   v=p->adjvex;
   DFSArticul(G,v); /* 從第v頂點(diǎn)出發(fā)深度優(yōu)先查找關(guān)節(jié)點(diǎn) */
   if(count<G.vexnum) /* 生成樹的根有至少兩棵子樹 */
   {
     printf("%d %s\n",0,G.vertices[0].data); /* 根是關(guān)節(jié)點(diǎn)，輸出 */
     while(p->nextarc)
     {
       p=p->nextarc;
       v=p->adjvex;
       if(visited[v]==0)
         DFSArticul(G,v);
     }
   }
 }

 void main()
 {
   int i;
   ALGraph g;
   printf("請(qǐng)選擇無向圖\n");
   CreateGraph(&g);
   printf("輸出關(guān)節(jié)點(diǎn)：\n");
   FindArticul(g);
   printf(" i G.vertices[i].data visited[i] low[i]\n");
   for(i=0;i<g.vexnum;++i)
     printf("%2d %9s %14d %8d\n",i,g.vertices[i].data,visited[i],low[i]);
 }