寻找割点是深度优先搜索（DFS）的应用。
简要来说：
第3点实质上意味着该节点是一个割点。
现在对于一个孩子，这条到达节点祖先的路径将通过从它或其任何子节点之一出发的后向边来实现。
所有这些都在这个PDF中精美地解释了。
我将尝试以直观的方式解释该算法如何工作，并给出带注释的伪代码，输出双连通分量和桥。
实际上，可以为关节点开发蛮力算法。只需取出一个顶点，在图上运行BFS或DFS。如果保持连接，则该顶点不是关节点，否则它就是。这将在O（V（E + V））= O（EV）时间内运行。挑战在于如何在线性时间（即O（E + V））内完成此操作。
关节点连接两个（或多个）子图。这意味着没有从一个子图到另一个子图的边缘。因此，想象一下你在其中一个子图中并访问其节点。当您访问该节点时，您会标记它，然后使用某些可用边缘移动到下一个未被标记的节点。当您这样做时，如何知道您仍在同一个子图中？这里的见解是，如果您在同一个子图中，则在访问未标记的节点时，您最终会通过边缘看到已标记的节点。这称为反向边缘，并指示您有一个循环。一旦找到反向边缘，您可以确信所有通过那个已标记节点到您正在访问的节点的节点都是同一个子图的一部分，并且其中没有关节点。如果您没有看到任何反向边缘，则迄今为止访问的所有节点都是关节点。
因此，我们需要一种算法，该算法会访问顶点并标记目标边缘之间的所有点作为当前正在访问的节点在同一个子图中。很明显可能存在子图中的子图，因此我们需要选择到目前为止最大的子图。这些子图称为双连通分量。我们可以通过分配每个双连通分量的ID来实现此算法，该ID初始化为迄今为止访问的顶点数的计数。稍后，当我们找到反向边缘时，我们可以将双连通分量ID重置为迄今为止发现的最低ID。
我们显然需要两次传递。在第一遍中，我们要弄清楚从每个顶点通过反向边缘可以看到哪个顶点（如果有）。在第二遍中，我们想以相反的方向访问顶点并收集最小的双连通分量ID（即从任何后代可访问的最早祖先）。DFS自然适合于此处。在DFS中，我们先向下再回来，因此可以使用单个DFS遍历完成上述两次传递。
现在，不再拖延，以下是伪代码：
time = 0
visited[i] = false for all i
GetArticulationPoints(u)
visited[u] = true
u.st = time++
u.low = v.st //keeps track of highest ancestor reachable from any descendants
dfsChild = 0 //needed because if no child then removing this node doesn't decompose graph
for each ni in adj[i]
if not visited[ni]
GetArticulationPoints(ni)
++dfsChild
parents[ni] = u
u.low = Min(u.low, ni.low) //while coming back up, get the lowest reachable ancestor from descendants
else if ni <> parent[u] //while going down, note down the back edges
u.low = Min(u.low, ni.st)
//For dfs root node, we can't mark it as articulation point because
//disconnecting it may not decompose graph. So we have extra check just for root node.
if (u.low = u.st and dfsChild > 0 and parent[u] != null) or (parent[u] = null and dfsChild > 1)
Output u as articulation point
Output edges of u with v.low >= u.low as bridges
output u.low as bicomponent ID
ni <> parent[u]，那会很有帮助。 - abhiarora有一个似乎被所有说明遗漏的事实：
事实1：在深度优先搜索生成树（DFSST）中，每个返祖边将一个顶点连接到其祖先之一。
这对于算法的工作至关重要，这也是任意生成树不适用于该算法的原因。这也是根节点是割点的原因，当且仅当它有多于1个子节点时：不能在跨越树的根节点子树之间存在返祖边。
有关该语句的证明如下：假设（u，v）是一条返祖边，其中u不是v的祖先，（WLOG）u在DFS中先访问，然后p是u和v的最深公共祖先，那么DFS必须先访问p，然后访问u，然后再次访问p，然后才能访问v。但是在访问v之前无法重新访问p，因为u和v之间有一条边。
将V（c）称为DFSST中以c为根的子树的顶点集合
将N（c）称为具有V（c）（通过边缘或返祖边）内部邻居的顶点的集合
事实2：
对于非根节点u，
如果u有一个孩子c，使得N（c）⊆V（c）∪{u}，那么u是割点。
原因：对于V（c）中的每个顶点w，从根到w的每条路径都必须包含u。否则，由于事实1，这样的路径必须包含连接u的祖先和u的后代的返祖边，从而使N（c）大于V（c）。
事实3：
事实#2的逆命题也是正确的。
原因：u的每个后代都具有不通过u的通向根的路径。 在V（c）中的后代可以通过连接V（c）与N（c）/ V（c）之间的返祖边来绕过u。
因此，对于算法，您只需要知道每个非根节点u的两件事：
因此，如果顶点u有一个孩子c，且L(c)小于D(u)，则意味着以c为根的子树具有到达u的祖先的返祖边，从而根据事实3不是割点。反过来也是基于事实2。
int adjMatrix[256][256];
int low[256], num=0, dfsnum[256];
void cutvertex(int u){
low[u]=dfsnum[u]=num++;
for (int v = 0; v < 256; ++v)
{
if(adjMatrix[u][v] && dfsnum[v]==-1)
{
cutvertex(v);
if(low[v]>dfsnum[u])
cout<<"Cut Vertex: "<<u<<"\n";
low[u]=min(low[u], low[v]);
}
else{
low[u]=min(low[u], dfsnum[v]);
}
}
}