SHARE
TWEET

Untitled

a guest Oct 13th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # put your python code here
  2. import sys
  3. import queue
  4. sys.setrecursionlimit(10000)
  5.  
  6. def breadthFirstSearch(V, Q:queue.Queue):
  7.     vertex = Q.get()
  8.     vertex[2] += 1
  9.     for i in range(len(vertex[1])):
  10.         child = V[vertex[1][i]]
  11.         if child[0] == 0:
  12.             child[0] = 1
  13.             child[2] = vertex[2]
  14.             Q.put(child)
  15.  
  16.     if not Q.empty():
  17.         breadthFirstSearch(V, Q)
  18.  
  19.  
  20. reader = sys.stdin
  21. vertexCount, edgesCount = tuple(map(int, next(reader).strip().split()))
  22. V = []
  23. for i in range(vertexCount):
  24.     V.append([0, [], -1])
  25. for i in range(edgesCount):
  26.     v1, v2 = tuple(map(int, next(reader).strip().split()))
  27.     V[v1][1].append(v2)
  28.     V[v2][1].append(v1)
  29.  
  30. Q = queue.Queue()
  31. Q.put(V[0])
  32. V[0][0] = 1
  33.  
  34. breadthFirstSearch(V, Q)
  35. for i in range(len(V)):
  36.     print(V[i][2], end=' ')
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top