Answer to Question #300540 in Python for Nisekoi

Question

Given an input undirected graph, write a program to find all articulation points in the graph. An articulation point is a vertex whose removal disconnects the graph. (Assume that the input graph is connected.) If a graph has no articulation points, it is called a

biconnected graph.

Input Format: The input is a text file which describes an undirected graph. The first line of the file specifies n & m, the number of vertices and number of edges in the graph respectively. The next m lines specify the m edges of the graph, one line per edge. An edge is described by its end points. If the number of vertices is n, assume that the vertices of the graph are numbered (0,1,..n-1).Input in terminal taken as python main.py ./input.txt

Output Format: Print “Biconnected Graph” if the input graph has no articulation points. If articulation points are found, print the vertices which are the articulation points.

Sample Input 1:

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

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=" ")