1 / 3
Jan 2021

This code is giving me runtime error NZEC. When I tried this on my IDE, I’m getting an error in the line if(visited_arr[i] == “not Visited”), list index out of range for v = 2. I tried thinking it hard, I’m not even getting close. How is it possible, coz I’ve marked all the vertices to be not visited initially, and for node 2, adjacent vertices are 1 and 3 which are also present in visited_arr. Please help

from collections import defaultdict

class Graph:

    def __init__(self,n_vertices):
        self.V = n_vertices
        self.graph = defaultdict(list)


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


    def iscycle(self,v,visited_arr,parent):
        visited_arr[v] = "Visited"
        for i in self.graph[v] :
            if(visited_arr[i] == "not Visited") :
                print(i)
                if (self.iscycle(i,visited_arr,v)):
                    return True
            elif i != parent:
                return True
        print(v)
        return False


    def is_tree(self):
        visited_arr = ["not Visited"] * self.V
        if (self.iscycle(1,visited_arr,0)) :
            print("isCycle function gives true")
            return False
        for i in  range(self.V) : 
            if(visited_arr[i] == "not Visited"):
                print("Node unvisited")
                return False
        print("gonna return true")
        return True


n , m = [int(x) for x in input().split()]

g = Graph(n)

for i in range(m):
    v , w = [int(x) for x in input().split()]

    g.add_edge(v,w)

if (g.is_tree()):
    print("YES")

else:
    print("NO")
  • created

    Jan '21
  • last reply

    Jan '21
  • 2

    replies

  • 576

    views

  • 2

    users

  • 1

    link

That will be because Python arrays are 0 based, but the problem uses 1 based indexes.

I added

v=v-1
w=w-1

between the reading and adding to the graph, and the NZEC no longer occurred.

PT07Y2