Я попробовал эту первую проблему в поисковой практике от hackerearth (ссылка на проблему) . Мой код прошел тестовый пример. Но я что-то упускаю, когда дело доходит до сдачи тестовых случаев.
Я выполнил «мои выходные данные» и «тестовые выходные данные» через программу расстояний для документов, которую я закодировал (для первого входного ввода), и было найдено, что расстояние составляет ~ 0,52 (градус) [0 град., Означающее документы точно так же, и 90 градусов, что означает, что документы совершенно разные]. Это было сделано только для того, чтобы приблизительно измерить, насколько я ошибался. Мне нужна помощь, чтобы выяснить, в каких случаях я не могу учесть в своем коде.
описание проблемы:
На сайте социальной сети люди связаны с другими людьми. Вся система выглядит как гигантский связный граф. В этом вопросе вам необходимо ответить на общее количество людей, подключенных в t узлах друг от друга (t в удаленности). Например: два человека, напрямую соединенные, находятся на расстоянии 1. В то время как два человека, имеющие общий контакт без прямой связи, находятся на расстоянии двух соединений.
Первая строка входной строки содержит два целых числа n и e, где n - узлы, а e - ребра. Следующая строка e будет содержать два целых числа u и v, означающие, что узел u и узел v связаны друг с другом ненаправленным образом. Следующая строка содержит одно целое число m, которое является количеством запросов. Следующие m строк, каждая из которых имеет два входа, один в качестве исходного узла, а другой в качестве требуемого t-соединения, которое должно использоваться для обработки запроса.
Примечание. Индекс узлов будет основан на 0. Показанный пример и контрольный пример имеют индекс на основе 1. Для отправки решения используйте индексирование на основе 0.
пример ввода:
9 10
1 2
2 3
1 7
2 4
3 4
4 7
7 8
9 7
7 6
5 6
3
4 2
5 3
2 1
выход:
4
4
3
Объяснение
После создания графика было 3 запроса,
я. Исходный узел: 4, и мы должны выяснить общее количество узлов на расстоянии 2 от узла 4.
1 (4-> 2-> 1), 8 (4-> 7-> 8), 9 (4-> 7-> 9), 6 (4-> 7-> 6) = 4
II. Как и выше
III. Исходный узел: 2, и мы должны выяснить общее количество узлов на расстоянии 1 от узла 2.
1 (2-> 1), 4 (2-> 4), 3 (2-> 3) = 3
ссылка для входного графического изображения
#social network bfs algorithm
from collections import deque
graph = {}
queries = []
def accept_values():
#accept number of vertices and edges
vertex_edge = [int(i) for i in input().strip().split(" ")]
#accept the edges for the undirected graph
for i in range(vertex_edge[1]):
edge = [int(i) for i in input().strip().split(" ")]
try:
graph[edge[0]].append(edge[1])
except:
graph[edge[0]] = [edge[1]]
try:
graph[edge[1]].append(edge[0])
except:
graph[edge[1]] = [edge[0]]
#accepting the number of queries and the queries themselves
number_of_queries = int(input())
for i in range(number_of_queries):
queries.append([int(i) for i in input().strip().split(" ")])
#applying bfs on the (source, required distance) queries
for query in queries:
bfs(query)
def bfs(query):
counter = 0
q = deque()
q.append(query[0])
visited = {query[0] : True}
distance = {query[0] : 0}
while q:
popped = q.popleft()
for neighbour in graph[popped]:
if neighbour not in visited:
visited[neighbour] = True
#stop looking further because we have all the nodes at the required distance, i think
if distance[popped] + 1 > query[1]:
for key in distance:
if distance[key] == query[1]:
counter +=1
print(counter)
return
#keep going until we reach the required query distance
else:
distance[neighbour] = distance[popped] + 1
q.append(neighbour)
#prints 0 if there are no such nodes
print(counter)
#calling function to accept values as per required format
accept_values()