title: Optimize Breadth First Search
body: <p>I have been getting timeout errors for this particular graph theory <a href="https://www.hackerrank.com/challenges/rust-murderer" rel="nofollow noreferrer">problem</a>. I tried optimizing my code as much as I could but it's still not meeting the HackerRank performance standards for this problem. To give you a basic run down, I first assume a fully connected graph and run a BFS on it, avoiding the edges which are city roads. But instead of creating the actual graph for every test case, I made a generator which lets my BFS function iterate through only the nodes to which the current node is connected by a village edge. Any hint on how I can optimize it more would be appreciated.</p>
  
  <pre><code>from collections import deque
  T = input()
  
  # BFS
  def return_nodes(N,a,edges):
      for i in xrange(1,N+1):
          if i != a and (i,a) not in edges and (a,i) not in edges:
              yield i
  
  def bfs(start,N,edges):
      S,q,dist = set(),deque(),{}
      S.add(start)
      q.append(start)
      dist[start] = 0
      while q:
          current_node = q.popleft()
          for i in return_nodes(N,current_node,edges):
              if i in S: continue
              S.add(i)
              q.append(i)
              dist[i] = dist[current_node] + 1
      return dist
  
  for i in xrange(T):
      N,M = map(int,raw_input().split())
      # Main roads/edges
      main_edges = set()
      for j in xrange(M):
          a,b = map(int,raw_input().split())
          main_edges.add((a,b))
      start = input()
      dist = bfs(start,N,main_edges)
      for k in dist:
          if k != start:
              print dist[k],
      print " "
  </code></pre>