title: bfs social network algorithm(graph algorithm) - hackerearth
body: <p>I tried this breadth first search practice problem from hackerearth<a href="https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/social-networking-graph/" rel="nofollow noreferrer">(link to problem)</a>. My code passed the sample test case. But I am missing something when it comes to the submission test cases. </p>
  
  <p>I ran "my output" and the "test output" through a document distance program that i coded up(for the first submission input), and the distance was found to be ~ 0.52 (deg) [0 deg meaning the documents are exactly same, and 90 deg meaning the documents are entirely different]. This was done only to approximately measure how wrong i was. I need help to find what case(s) I'm failing to account for in my code.</p>
  
  <p><strong>problem description:</strong></p>
  
  <p>In a social networking site, people are connected with other people. The whole system appears as a giant connected graph. In this question, you are required to answer the total number of people connected at t nodes away from each other (t distance connectivity). For example: Two persons directly connected are at 1 distance connectivity. While the two persons having a common contact without having direct connectivity, are at 2 distance connectivity.</p>
  
  <p>First line of input line contains, two integers n and e, where n is the nodes and e are the edges. Next e line will contain two integers u and v meaning that node u and node v are connected to each other in undirected fashion. Next line contains single integer, m, which is number of queries. Next m lines, each have two inputs, one as source node and other as a required t distance connectivity which should be used to process query.</p>
  
  <p>Note: The index of nodes will be 0-based. The example and the test case shown is of 1-based index. For submitting the solution, use 0-based indexing.</p>
  
  <p><strong>sample input:</strong></p>
  
  <p>9 10</p>
  
  <p>1 2</p>
  
  <p>2 3</p>
  
  <p>1 7</p>
  
  <p>2 4</p>
  
  <p>3 4</p>
  
  <p>4 7</p>
  
  <p>7 8</p>
  
  <p>9 7</p>
  
  <p>7 6</p>
  
  <p>5 6</p>
  
  <p>3</p>
  
  <p>4 2</p>
  
  <p>5 3</p>
  
  <p>2 1</p>
  
  <p><strong>output:</strong></p>
  
  <p>4</p>
  
  <p>4</p>
  
  <p>3</p>
  
  <p><strong>Explanation</strong>
  After creating the graph, there was 3 queries,</p>
  
  <p>i. Source node: 4, and we have to find out total number of nodes at a distance of 2 from node 4.
  1(4->2->1), 8(4->7->8), 9(4->7->9), 6(4->7->6) = 4</p>
  
  <p>ii. Similarly as above</p>
  
  <p>iii. Source node: 2, and we have to find out total number of nodes at a distance of 1 from node 2.
  1(2->1), 4(2->4), 3(2->3) = 3</p>
  
  <p><a href="https://i.stack.imgur.com/Luzyj.png" rel="nofollow noreferrer">link for input graph image</a></p>
  
  <pre><code>#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 &gt; 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()
  </code></pre>