时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

图的割点(Articulation Points)、桥(Bridge)、双连通分量(Biconnected Components)

• 图的割点(Articulation-Points)

图的割点也叫图的关节点，定义为无向图中分割两个连通分量的点，或者说去掉这个点，图中的连通分量数增加了。可以看到如果求出了连通分量，那么不同连通分量中间的顶点就是割点。什么时候某个顶点不是这样的割点？如果这个顶点的子孙顶点有连接这个顶点祖先顶点的边，那么去掉这个顶点，这个顶点的子孙顶点和祖先顶点仍然连通。那么，寻找割点的过程就等价于寻找子孙顶点没有连接祖先顶点的顶点。这个问题的求解过程类似于Tarjan强连通分量的求解过程。

不过，这个问题有个例外就是根顶点，对一般顶点的处理方式处理根顶点行得通吗？根顶点肯定没有子孙顶点指向祖先顶点，但是根顶点可以是割点。所以，根顶点需要特殊处理。根顶点什么时候是割点？当根顶点有多颗子树，且之间无法互相到达的时候。那么，存不存在根顶点有多颗子树，且之间可以互相到达？不存在，如果互相之间可以到达，那在根顶点搜索第一颗子树的时候，就会搜索到可到达的子树，就不会存在多颗子树了。所以，根顶点有多颗子树，那么这多颗子树之间一定无法互相到达。根顶点有多颗子树，且之间无法互相到达的时候就等价于根顶点有多颗子树。所以，只要根顶点有多颗子树，那么根顶点就是割点。

同样地，数组disc表示顶点被访问顺序的编号，数组low表示顶点所在的强连通分量编号。数组parent找出根顶点。

伪代码：
ARTICULATION-POINTS(g)
  let disc be new Array
  let low be new Array
  let result be new Array
  let parent be new Array
  let visited be new Array
  for i from 1 to the number of vertex in g
    result [i] = false
    visited [i] = false
    parent [i] = -1
  end
  for u from 1 to the number of vertex in g 
    if visited[i] == false
      ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)
  end
  for i from 1 to the number if vertex in g
    if result[i] == true
      print '\n Found a Articulation Points i \n'
  end
  
ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)
  let time be static
  time = time + 1
  let children = 0
  disc[u] = low[u] = time
  visited[u] = true
  for v equal to every vertex adjacent to u
    if visited[v] == false
      children = children + 1
      parent[v] = u
      ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)
      low[u] = min(low[u],low[v])
      if parnet[u] == -1 and children > 1
        result[u] = true
      if parent[u] != -1 and low[v] >= disc[u]
        result[u] = true
    else if v != parent[u]
      low[u] = min(low[u],disc[v])
  end

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

• 桥(Bridge)

桥定义为一条边，且去掉这个边，图中的连通分量数增加了。类似于寻找割点，寻找桥就是寻找这样一条，一端的顶点的子孙顶点没有连接这个顶点和其祖先顶点的边。求解过程和求割点基本一致。