Given an undirected graph G $=($V$,$ E$)$ with n vertices and m edges, and a positive

$($not necessarily unique$)$ edge cost ce for each edge in E$.$ We are also given q pairs

of vertices Q $=\{($u$1,$ v$1),...,($uq$,$ vq$)\}.$ Decide for each pair $($u$,$ v$)$ in Q if there is a

path between u and v in G$.$

Task: Design an algorithm that solves this problem in O$($q $($m $+$ n$))$ time.

Implementation and Testing: Implement your algorithm $($in Ed$)$ and test it on

the following graph instances: Graph$8,$ Graph$250,$ Graph$1000.$ Each instance is

given as a text file using the following format:

n

m

vertexId vertexId weight

vertexId vertexId weight

$...$

vertexId vertexId weight

q

vertexId vertexId

vertexId vertexId

$...$

For example, the text below describes the instance depicted in Fig. $1.$ Note that

the vertices are numbered from $0$ to n $1$ and that the two queries are $(0,1)$ and

$(0,2).$

$4$

$3$

$022$

$035$

$233$

$2$

$01$

$02$

Your program should read input from the text file. Your program only needs to

print out $1(=$ yes, there is a path in G between u and v$)$ or $0(=$ no$,$ there is no

path connecting u and v in G$)$ for each of the q query pairs. You should separate

each $1/0$ with a new line. A scaffold is provided for Python for you.

Your code will not be benchmarked or tested for time complexity, but for full

points it must be able to run instances similar to $$Graph$1000,$ and each test will

time out after $5$ seconds. Your program will also be tested on several hidden test

cases.

If the query is $(0,1)$ on the figure $1$ below then the answer should be $0$ while

the answer to the query $(0,2)$ on the same graph should be $1.$

Below is the scaffold provided

# Read in the number of vertices $($n$)$ and edges $($m$)$

n $=$ int$($input$())$

m $=$ int$($input$())$

edges, queries $=[],[]$

for $\_$ in range$($m$)$:

edges.append$($input$().$split$())$

q $=$ int$($input$())$

for $\_$ in range$($q$)$:

queries.append$($input$().$split$())$

# Print a $`1`$ to stdout for each query. This section should be altered to instead print a $`1`$ where the

# query indicates a connection and $`0`$ else.

for $\_$ in queries:

print$($int$($True$))$