我能够编写一个我认为可能有效的算法。它如下:我们有任意顶点的四种状态:未访问、访问中、已访问和重新访问。我们保持一个父数组和一个计数未连接子项的数组。1. 我们从根开始不断向栈中添加顶点,但不弹出父元素。例如,我们有将根1连接到2、3、6和7,那么我们将1推入栈中,但不弹出它。相反,我们将其他子项放在其顶部。我们还为每个元素维护父项。例如,2、3、6、7的父项为1。2. 如果某些元素处于未访问状态,则我们将堆栈上的节点标记为访问中。3. 如果在任何节点的邻接列表遍历期间发现某个元素处于访问中状态,则仅当此元素不是其父项时,我们将其状态更改为重新访问。例如,以上所有2、3、6、7都处于访问中状态。如果7的邻接列表为1、3、5、10、8、12,则由于1是其父项,因此我们不会更改1的状态。我们转到3并查看其状态为VISITING,并且也不是7的父项,因此我们将其状态更改为REVISITING。此时,栈从底部到顶部为1、2、3、6、7、5、10、8、12。4. 现在,如果我们遇到任何元素,在其邻接列表中没有未访问的元素,则如果此元素的状态为VISITING状态(不是REVISITING),我们将其父项的子元素总数加1(初始化为0)。如果它是REVISITING状态,我们忽略将1添加到其父项的子级编号中。同时,我们弹出该元素并将其状态更改为已访问。5. 逐步弹出元素,我们到达根的子项(连接或唯一)。我们通过第4步检查计算根节点的唯一未连接子项数。如果大于1,则根是关节点。虽然这个算法似乎有些复杂,但它似乎有效。欢迎提出任何建议或问题。