Problem :

https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem


My Solution :

#!/usr/bin/env python3


class Graph(object):
    def __init__(self, n):
        self.total_nodes = n
        self.graph = {}

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

    def find_all_distances(self, s):
        distances = {s: 0}
        queue = []
        visited = [0] * (self.total_nodes + 1)
        queue.append(s)
        visited[s] = 1
        while queue:
            node = queue.pop(0)
            for neighbor in self.graph.get(node, []):
                if not visited[neighbor]:
                    queue.append(neighbor)
                    visited[neighbor] = 1
                    distances[neighbor] = distances[node] + 6
        for i in range(1, self.total_nodes + 1):
            if i == s:
                continue
            yield distances.get(i) or -1


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    graph = Graph(n)
    for _ in range(m):
        u, v = map(int, input().split())
        graph.connect(u, v)
    s = int(input())
    print(' '.join(map(str, graph.find_all_distances(s))))