Graph Shortest Path Class (OOP)

Graph Shortest Path Class (OOP)

Hard Programming Interview OOP 25 views
Explanation Complexity

Problem Statement

We have {x}. Create Graph class with bfs(s,t) method. Output shortest distance or -1.

Input Format

First line n m. Next m lines u v. Last line s t.

Output Format

One integer distance.

Example

5 5
1 2
2 3
3 4
4 5
1 5
1 4
3

Constraints

1

Input / Output Format

Input Format
First line n m. Next m lines u v. Last line s t.
Output Format
One integer distance.
Constraints
1

Examples

Input:
5 5 1 2 2 3 3 4 4 5 1 5 1 4
Output:
3

Example Solution (Public)

Programming Interview 
import sys
from collections import deque
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
it=iter(p)
n=int(next(it)); m=int(next(it))
class Graph:
  def __init__(self,n):
    self.n=n
    self.g=[[] for _ in range(n+1)]
  def add(self,u,v):
    self.g[u].append(v)
    self.g[v].append(u)
  def bfs(self,s,t):
    dist=[-1]*(self.n+1)
    q=deque([s])
    dist[s]=0
    while q:
      u=q.popleft()
      if u==t:
        return dist[u]
      for v in self.g[u]:
        if dist[v]==-1:
          dist[v]=dist[u]+1
          q.append(v)
    return -1
G=Graph(n)
for _ in range(m):
  u=int(next(it)); v=int(next(it))
  G.add(u,v)
s=int(next(it)); t=int(next(it))
print(G.bfs(s,t))

Official Solution Code

import sys
from collections import deque
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
it=iter(p)
n=int(next(it)); m=int(next(it))
class Graph:
  def __init__(self,n):
    self.n=n
    self.g=[[] for _ in range(n+1)]
  def add(self,u,v):
    self.g[u].append(v)
    self.g[v].append(u)
  def bfs(self,s,t):
    dist=[-1]*(self.n+1)
    q=deque([s])
    dist[s]=0
    while q:
      u=q.popleft()
      if u==t:
        return dist[u]
      for v in self.g[u]:
        if dist[v]==-1:
          dist[v]=dist[u]+1
          q.append(v)
    return -1
G=Graph(n)
for _ in range(m):
  u=int(next(it)); v=int(next(it))
  G.add(u,v)
s=int(next(it)); t=int(next(it))
print(G.bfs(s,t))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.