Answer to Question #301363 in Python for eranna

Question

Given an input undirected graph, write a program to find all articulation points in tgraph. An

articulation point is a vertex whose removal disconnects graph. (Assume that input graph is

connected.) If a graph has no articulation points, it is called a biconnected graph.

Input Format: input text file which describes an undirected graph. first line of file

specifies n & m, number of vertices and number of edges in the graph respectively.next m

lines specify the m edges of graph, one line per edge. An edge is described by its end points. If

number of vertices is n, assume vertices of graph are numbered (0,1,..n-1).

Output Format: Print “Biconnected Graph” if input graph has no articulation points. If

articulation points are found, print vertices articulation points.

Sample Input 1 (for graph shown on the right):

7 8

0 1

0 2

2 1

2 3

4 2

3 5

4 6

5 6

Sample Output 1

Articulation points found:

2

Sample Input 2 (for the graph shown on the right):

4 4

0 1

1 2

2 3

3 0

Sample Output 2

Biconnected Graph

Answer 1

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.vertex = vertices  # No. of vertices
        self.graph = defaultdict(list)  # default dictionary to store graph
        self.t = 0

    def addEdge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def articular_point_recursive(self, u, was, ap, parent, min, d):
        child = 0
        was[u] = True
        d[u] = self.t
        min[u] = self.t
        self.t += 1
        for i in self.graph[u]:
            if not was[i]:
                parent[i] = u
                child += 1
                self.articular_point_recursive(i, was, ap, parent, min, d)
                min[u] = min(min[u], min[i])
                if parent[u] == -1 and child > 1:
                    ap[u] = True
                if parent[u] != -1 and min[i] >= d[u]:
                    ap[u] = True
            elif i != parent[u]:
                min[u] = min(min[u], d[i])
                
    def articular_point(self):
        was = [False] * (self.vertex)
        d = [float("Inf")] * (self.vertex)
        min = [float("Inf")] * (self.vertex)
        p = [-1] * (self.vertex)
        art_point = [False] * (self.vertex)  # To store articulation points
        for i in range(self.vertex):
            if was[i] == False:
                self.articular_point_recursive(i, was, art_point, p, min, d)

        for i, j in enumerate(art_point):
            if j == True:
                print(i, end=" ")