题目：求一个连通图的割点，割点的定义是，如果除去此节点和与其相关的边，图不再连通，描述算法。

分析：

1. 最简单也是最直接的算法是，删除一个点然后判断连通性，如果删除此点，图不再连通，则此点是割点，反之不是割点（图的连通性一般通过深搜来判定，是否能一次搜索完 全部顶点）；

2. 通过深搜优先生成树来判定。从任一点出发深度优先遍历得到优先生成树，对于树中任一顶点Ｖ而言，其孩子节点为邻接点。由深度优先生成树可得出两类割点的特性：

     （１）若生成树的根有两棵或两棵以上的子树，则此根顶点必为割点。因为图中不存在连接不同子树顶点的边，若删除此节点，则树便成为森林；

     （２）若生成树中某个非叶子顶点V，其某棵子树的根和子树中的其他节点均没有指向V的祖先的回边，则V为割点。因为删去v，则其子树和图的其它部分被分割开来。

仍然利用深搜算法，只不过在这里定义visited[v]表示为深度优先搜索遍历图时访问顶点v的次序号，定义low[v]=Min{visited[v]，low[w]，visited[k]}，其中w是顶点v在深度优先生成树上的孩子节点；k是顶点v在深度优先生成树上由回边联结的祖先节点。

   割点判定条件：如果对于某个顶点v，存在孩子节点w且low[w]>=visited[v]，则该顶点v必为关节点。因为当w是v的孩子节点时，low[w]>=visited[v]，表明w及其子孙均无指向v的祖先的回边，那么当删除顶点v后，v的孩子节点将于其他节点被分割开来，从来形成新的连通分量。

#include 
    
       #include 
     
        #include 
      
         using namespace std;    #define MAXN 100    struct ArcNode  {      int adjVertex;       //边到的顶点      ArcNode *next;  };    struct VNode  {      string data;      ArcNode *firstArc;  };    typedef VNode AdjList[MAXN];    struct Graph  {      int vertexNum;      int arcNum;      AdjList vertexs;  };    int Locate(Graph g,string str)  {      for(int i = 0;i
       
        >g.vertexNum>>g.arcNum;        for(int i = 0;i
        
         >g.vertexs[i].data;          g.vertexs[i].firstArc = NULL;      }        for(int i = 0;i 
         
          >start>>end; int m = Locate(g,start); int n = Locate(g,end); ArcNode *node = new ArcNode; node->adjVertex = n; node->next = g.vertexs[m].firstArc; g.vertexs[m].firstArc = node; ArcNode *node1 = new ArcNode; node1->adjVertex = m; node1->next = g.vertexs[n].firstArc; g.vertexs[n].firstArc = node1; } } void Print(Graph g) { for(int i = 0;i
          
           "<
           
            adjVertex].data; p = p->next; } cout <
            
             adjVertex; else return -1; } int NextAdjVex(Graph g,int v,int w) //返回顶点v相对于w的下一个邻接点的序号 { ArcNode *p = g.vertexs[v].firstArc; while(p) { if(p->adjVertex == w) break; p = p->next; } if(p->adjVertex !=w || !p->next) return -1; return p->next->adjVertex; } //求割点 int countN; int visted[MAXN]; int low[MAXN]; void DFSCutPoint(Graph g,int v0) { int min = 0,w; visted[v0] = min = ++countN;;//v0是第count个访问的顶点，min的初值为visited[v0]，即v0的访问次序 for(ArcNode *p = g.vertexs[v0].firstArc;p;p=p->next) { w = p->adjVertex; if(!visted[w]) { DFSCutPoint(g,w);//从第w个顶点出发深搜，查找并输出关节点（割点），返回前求得low[w] if(low[w] < min)//如果v0的孩子节点w的low[]小，说明孩子节点还与其他节点（祖先）相邻 min = low[w]; if(low[w]>=visted[v0] ) //v0的孩子节点w只与v0相连，则v0是关节点（割点） cout<
             
              <<" "; } else if(visted[w] < min)//w已访问，则w是v0生成树上祖先，它的访问顺序必小于min min =visted[w]; } low[v0] = min;//low[v0]取三者最小值 } void FindCutPoint(Graph g) { visted[0] = true; for(int i = 1;i
              
               adjVertex; DFSCutPoint(g,v); if(countN < g.vertexNum) { cout << g.vertexs[0].data<<" "; while(p->next) { p = p->next; v = p->adjVertex; if(!visted[v]) DFSCutPoint(g,v); } } } int main() { Graph g; Create(g); cout<<"割点如下: "<