We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

import math
import os
import random
import re
import sys
from collections import defaultdict

This class represents a directed graph

using adjacency list representation

class Graph:

# Constructor
def __init__(self):
# Default dictionary to store graph
self.graph = defaultdict(list)
# Function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)
# Function to print a BFS of graph
def BFS(self, s):
dico = dict()
# Mark all the vertices as not visited
visited = [False] * (max(self.graph) + 1)
# Create a queue for BFS
queue = []
queue0 = []
# Mark the source node as
# visited and enqueue it
if (s not in self.graph):
print(-1)
dico[s]=-1
return dico
queue.append(s)
queue0.append(0)
visited[s] = True
cmpt=1
l=[0]
k=0
dico = dict()
while queue:
# Dequeue a vertex from
# queue and print it
s = queue.pop(0)
print(s,end=" ")
#s0=queue0.pop(0)
print(l[k]*cmpt)
dico[s]=l[k]*cmpt
k+=1
# Get all adjacent vertices of the
# dequeued vertex s.
# If an adjacent has not been visited,
# then mark it visited and enqueue it
maxp=max(l)
for i in self.graph[s]:
if visited[i] == False:
l.append(maxp+1)
queue.append(i)
visited[i] = True
return dico

Complete the findShortest function below.

#

For the weighted graph, :

#

1. The number of nodes is _nodes.

2. The number of edges is _edges.

3. An edge exists between _from[i] to _to[i].

#
#
def findShortest(graph_nodes, graph_from, graph_to, ids, val):
# solve here
n= graph_nodes
g = Graph()
for i in range(len(graph_from)):
g.addEdge(graph_from[i],graph_to[i])
g.addEdge(graph_to[i],graph_from[i])
if ids.count(val)<=1:
return -1
dico = g.BFS(val)
for i in range(1,n+1):
if i not in dico.keys():
dico[i]=g.BFS(i)[i]
s=[]
for k in range(len(ids)):
if ids[k]==2 and dico[k+1]>0:
s.append(dico[k+1])
print(s)

return min(s)

if name == 'main':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

graph_nodes, graph_edges = map(int, input().split())
graph_from = [0] * graph_edges
graph_to = [0] * graph_edges
for i in range(graph_edges):
graph_from[i], graph_to[i] = map(int, input().split())
ids = list(map(int, input().rstrip().split()))
val = int(input())
ans = findShortest(graph_nodes, graph_from, graph_to, ids, val)
fptr.write(str(ans) + '\n')
fptr.close()

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website

## Find the nearest clone

You are viewing a single comment's thread. Return to all comments â†’

## !/bin/python3

import math import os import random import re import sys from collections import defaultdict

## This class represents a directed graph

## using adjacency list representation

class Graph:

## Complete the findShortest function below.

#

## For the weighted graph, :

#

## 1. The number of nodes is _nodes.

## 2. The number of edges is _edges.

## 3. An edge exists between _from[i] to _to[i].

# # def findShortest(graph_nodes, graph_from, graph_to, ids, val): # solve here n= graph_nodes g = Graph() for i in range(len(graph_from)): g.addEdge(graph_from[i],graph_to[i]) g.addEdge(graph_to[i],graph_from[i]) if ids.count(val)<=1: return -1 dico = g.BFS(val) for i in range(1,n+1): if i not in dico.keys(): dico[i]=g.BFS(i)[i] s=[] for k in range(len(ids)): if ids[k]==2 and dico[k+1]>0: s.append(dico[k+1]) print(s)

if

name== 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')