割点迭代算法

割点迭代算法（Iterative Cut-Vertex Algorithm）用于寻找无向图中的割点。割点是指删除该节点及其关联边后，图会被分成多个连通分量。以下是一个使用深度优先搜索（DFS）实现的割点迭代算法的代码示例：

def iterative_cut_vertex(graph):
    n = len(graph)
    visited = [False] * n
    disc = [float('inf')] * n
    low = [float('inf')] * n
    is_cut_vertex = [False] * n
    parent = [-1] * n
    time = 0
    
    def dfs(u):
        nonlocal time
        child_count = 0
        visited[u] = True
        disc[u] = time
        low[u] = time
        time += 1
        
        for v in graph[u]:
            if not visited[v]:
                parent[v] = u
                child_count += 1
                dfs(v)
                
                low[u] = min(low[u], low[v])
                
                if parent[u] == -1 and child_count > 1:
                    is_cut_vertex[u] = True
                
                if parent[u] != -1 and low[v] >= disc[u]:
                    is_cut_vertex[u] = True
            
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])
    
    for i in range(n):
        if not visited[i]:
            dfs(i)
    
    cut_vertices = [i for i, is_cut in enumerate(is_cut_vertex) if is_cut]
    return cut_vertices

使用示例：

graph = [[1, 2, 3], [0, 2], [0, 1], [0, 4], [3, 5], [4]]

cut_vertices = iterative_cut_vertex(graph)
print("Cut vertices:", cut_vertices)

上述代码中，我们使用深度优先搜索来遍历整个图。在每次访问一个节点时，我们记录其发现时间（disc）和最小后代发现时间（low）。如果一个节点的某个子节点的最小后代发现时间大于等于该节点的发现时间，并且该节点不是根节点，那么该节点就是一个割点。

最后，我们将所有割点存储在cut_vertices列表中并返回。在示例图中，割点为节点0和节点3。