// algo7-6.cpp 實現算法7.10、7.11的程序
 #include"c1.h"
 #include"func7-1.cpp" // 包括頂點信息類型的定義及對它的操作
 #include"func7-4.cpp" // 弧(邊)的相關信息類型的定義及對它的操作
 #include"c7-2'.h" // 圖的鄰接表存儲結構(與單鏈表的變量類型建立聯系)
 #include"bo7-2.cpp" // 圖的鄰接表存儲結構的基本操作

 int count,lowcount=1; // 全局量count對訪問順序計數,lowcount對求得low值的順序計數
 int low[MAX_VERTEX_NUM],lowOrder[MAX_VERTEX_NUM];
 // 全局數組，low[]存頂點的low值，lowOrder存頂點求得low值的順序
 int visited[MAX_VERTEX_NUM]; // 訪問標志數組(全局量)

 void DFSArticul(ALGraph G,int v0)
 { // 從第v0個頂點出發深度優先遍歷圖G，查找并輸出關節點。算法7.11
   int min,w;
   ArcNode *p;
   visited[v0]=min=++count; // v0是第count個訪問的頂點，min的初值為v0的訪問順序
   for(p=G.vertices[v0].firstarc;p;p=p->nextarc) // 依次對v0的每個鄰接頂點檢查
   { w=p->data.adjvex; // w為v0的鄰接頂點位置
     if(visited[w]==0) // w未曾訪問，是v0的孩子
     { DFSArticul(G,w);
       // 從第w個頂點出發深度優先遍歷圖G，查找并輸出關節點。返回前求得low[w]
       if(low[w]<min) // 如果v0的孩子結點w的low[]小，這說明孩子結點還與其他結點(祖先)相鄰
         min=low[w]; // 取min值為孩子結點的low[]，則v0不是關節點
       else if(low[w]>=visited[v0]) // v0的孩子結點w只與v0相連，則v0是關節點
         printf("%d %s\n",v0,G.vertices[v0].data.name); // 輸出關節點v0
     }
     else if(visited[w]<min) // w已訪問，則w是v0在生成樹上的祖先，它的訪問順序必小于min
       min=visited[w]; // 故取min為visited[w]
   }
   low[v0]=min; // v0的low[]值為三者中的最小值
   lowOrder[v0]=lowcount++;
   // 記錄v0求得low[]值的順序，總是在返回主調函數之前求得low[]。新增
 }

 void FindArticul(ALGraph G)
 { // 連通圖G以鄰接表作存儲結構，查找并輸出G上全部關節點。全局量count對訪問計數。算法7.10
   int i,v;
   ArcNode *p;
   count=1; // 訪問順序
   visited[0]=count; // 設定鄰接表上0號頂點為生成樹的根，第1個被訪問
   for(i=1;i<G.vexnum;++i) // 對于其余頂點
     visited[i]=0; // 其余頂點尚未訪問，設初值為0
   p=G.vertices[0].firstarc; // p指向根結點的第1個鄰接頂點
   v=p->data.adjvex; // v是根結點的第1個鄰接頂點的序號
   DFSArticul(G,v); // 從第v頂點出發深度優先查找關節點
   if(count<G.vexnum) // 由根結點的第1個鄰接頂點深度優先遍歷G，訪問的頂點數少于G的頂點數
   { // 說明生成樹的根有至少兩棵子樹，則根是關節點
     printf("%d %s\n",0,G.vertices[0].data.name); // 根是關節點，輸出根
     while(p->nextarc) // 根有下一個鄰接點
     { p=p->nextarc; // p指向根的下一個鄰接點
       v=p->data.adjvex;
       if(visited[v]==0) // 此鄰接點未被訪問
         DFSArticul(G,v); // 從此頂點出發深度優先查找關節點
     }
   }
 }

 void main()
 {
   int i;
   ALGraph g;
   char filename[13]; // 存儲數據文件名(包括路徑)
   printf("請輸入數據文件名：");
   scanf("%s",filename);
   CreateFromFile(g,filename); // 由文件構造無向圖g
   Display(g); // 輸出無向圖g
   printf("輸出關節點：\n");
   FindArticul(g); // 求連通圖g的關節點
   printf(" i G.vertices[i].data visited[i] low[i] lowOrder[i]\n"); // 輸出輔助變量
   for(i=0;i<g.vexnum;++i)
     printf("%2d %9s %14d %8d %8d\n",i,g.vertices[i].data.name,
     visited[i],low[i],lowOrder[i]);
 }