1 / 1
Dec 2020

I have implemented the code to find the articulation points using python anf tried submitting it but I am getting runtime error. I tried but I am not able to find the bug any help will be appreciated. Thank you

CODE

def count_cut_points(graph, root, time, low, tin, num_cut, visited, parent=-1):

# print(root)
visited[root] = 1
low[root] = tin[root] = time[0]
children = 0  # keeps track of how many children the current root node has
# the children are the nodes that are not discovered when we are
# in the adjacency list of root
time[0] += 1

for child in graph[root]:
    if child == parent:
        continue

    # already visited child
    # this child is my ancestor as it is already visted and it is not my parent
    # therefore it is poosible it was discovered before me
    if visited[child]:
        low[root] = min(low[root], tin[child])

    else:
        count_cut_points(graph, child, time, low,
                         tin, num_cut, visited, root)
        low[root] = min(low[root], low[child])

        # here root will be the articulation point
        # bridge mai only this condn changes to low[child] > tin[root] no equal to sign
        if low[child] >= tin[root] and parent != -1:
            #print("oye hoye", child, root)
            # one root can have multiple child that satisfy this condition
            # therefore use a set to store the unique points
            num_cut.add(root)

        children += 1

if parent == -1 and children > 1:
    num_cut.add(root)

while True:

nodes, edges = map(int, input().split())

if nodes == 0:
    exit()

graph = {u+1: [] for u in range(nodes)}
visited = [0]*(nodes+1)

for _ in range(edges):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

low = [0]*(nodes+1)
tin = [0]*(nodes+1)
time = [0]
num_cut = set()

# we will keep 1 as starting point for dfs
for i in range(1, nodes+1):
    if visited[i] == 0:
        count_cut_points(graph, i, time, low, tin, num_cut, visited, -1)

print(len(num_cut))