articulation points.txt

#articulation points
BEGIN

    CLASS Graph:

        FUNCTION __init__(vertices)
            V ← vertices
            graph ← empty adjacency list (defaultdict of lists)
            time ← 0
        END FUNCTION


        FUNCTION add_edge(u, v)
            ADD v TO graph[u]
            ADD u TO graph[v]        # undirected edge
        END FUNCTION


        FUNCTION dfs(u, visited, parent, low, disc, articulation_points)
            children ← 0
            visited[u] ← TRUE
            disc[u] ← time
            low[u] ← time
            time ← time + 1

            FOR each vertex v IN graph[u] DO
                IF visited[v] == FALSE THEN
                    parent[v] ← u
                    children ← children + 1
                    CALL dfs(v, visited, parent, low, disc, articulation_points)

                    # Update low value of u
                    low[u] ← MIN(low[u], low[v])

                    # ---- Case 1: Root with multiple children ----
                    IF parent[u] == -1 AND children > 1 THEN
                        ADD u TO articulation_points
                    ENDIF

                    # ---- Case 2: Non-root vertex with bridge condition ----
                    IF parent[u] ≠ -1 AND low[v] ≥ disc[u] THEN
                        ADD u TO articulation_points
                    ENDIF

                ELSE IF v ≠ parent[u] THEN   # Back edge
                    low[u] ← MIN(low[u], disc[v])
                ENDIF
            ENDFOR
        END FUNCTION


        FUNCTION find_articulation_points()
            visited ← array of size V initialized to FALSE
            disc ← array of size V initialized to ∞
            low ← array of size V initialized to ∞
            parent ← array of size V initialized to -1
            articulation_points ← empty set

            FOR i FROM 0 TO V-1 DO
                IF visited[i] == FALSE THEN
                    CALL dfs(i, visited, parent, low, disc, articulation_points)
                ENDIF
            ENDFOR

            RETURN articulation_points
        END FUNCTION




#code
from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.time = 0

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)  # undirected graph

    def dfs(self, u, visited, parent, low, disc, articulation_points):
        children = 0
        visited[u] = True
        disc[u] = low[u] = self.time
        self.time += 1

        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                children += 1
                self.dfs(v, visited, parent, low, disc, articulation_points)

                # Update low value
                low[u] = min(low[u], low[v])

                # Case 1: u is root of DFS tree and has more than one child
                if parent[u] == -1 and children > 1:
                    articulation_points.add(u)

                # Case 2: u is not root and low[v] >= disc[u]
                if parent[u] != -1 and low[v] >= disc[u]:
                    articulation_points.add(u)

            elif v != parent[u]:  # Back edge
                low[u] = min(low[u], disc[v])

    def find_articulation_points(self):
        visited = [False] * self.V
        disc = [float('inf')] * self.V
        low = [float('inf')] * self.V
        parent = [-1] * self.V
        articulation_points = set()

        for i in range(self.V):
            if not visited[i]:
                self.dfs(i, visited, parent, low, disc, articulation_points)

        return articulation_points


# ---------- MAIN PROGRAM ----------
if __name__ == "__main__":
    print("=== Articulation Point Finder ===")

    V = int(input("Enter number of vertices: "))
    E = int(input("Enter number of edges: "))

    g = Graph(V)

    print("\nEnter edges (u v) for an undirected graph (0-indexed):")
    for _ in range(E):
        u, v = map(int, input().split())
        g.add_edge(u, v)

    points = g.find_articulation_points()

    print("\nArticulation Points in the graph are:")
    if points:
        print(*sorted(points))
    else:
        print("No articulation points found.")