Articulation Point

A vertex in an undirected connected graph is an articulation point (or cut vertex) if removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more components

from collections import defaultdict
 
def articulation_points(graph):
    """
    Finds all articulation points in an undirected graph using Tarjan's algorithm.
    
    Args:
    - graph: a dictionary representing the graph, where the keys are the vertices and the values
             are lists of adjacent vertices.
    
    Returns:
    - a list of articulation points in the graph.
    """
    def dfs(node, parent, visited, disc, low, result):
        """
        A helper function to perform DFS on the graph and identify articulation points.
        """
        visited[node] = True
        disc[node] = low[node] = dfs.time
        dfs.time += 1
        
        children = 0
        for adj in graph[node]:
            if not visited[adj]:
                children += 1
                dfs(adj, node, visited, disc, low, result)
                
                low[node] = min(low[node], low[adj])
                
                if parent != -1 and low[adj] >= disc[node]:
                    result.add(node)
                    
                if parent == -1 and children > 1:
                    result.add(node)
                    
            elif adj != parent:
                low[node] = min(low[node], disc[adj])
            
    visited = defaultdict(bool)
    disc = defaultdict(int)
    low = defaultdict(int)
    result = set()
    dfs.time = 0
    
    for node in graph:
        if not visited[node]:
            dfs(node, -1, visited, disc, low, result)
    
    return list(result)
 
# Example graph
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3, 5],
    3: [2, 4],
    4: [3],
    5: [2, 6, 8],
    6: [5, 7],
    7: [6, 8],
    8: [5, 7],
}
 
# Find articulation points in the graph
result = articulation_points(graph)
 
# Print the result
print("Articulation points in the graph:", result)