You are viewing a single comment's thread. Return to all comments →
import os def rbfs(u, visited, adj, dist): queue =[(u, 0)] dist[u-1] = 0 visited[u-1] = True while queue: i, j = queue.pop(0) for k in adj[i]: if visited[k-1] == False: dist[k-1] = j+6 visited[k-1]= True queue.append((k, j+6)) return dist def bfs(n, m, edges, s): adjList ={v: [] for v in range(1, n+1)} for x, y in edges: adjList[x].append(y) adjList[y].append(x) visited = [False]*n distance = [-1]*n rbfs(s, visited, adjList, distance) distance.pop(s-1) return distance if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') q = int(input().strip()) for q_itr in range(q): first_multiple_input = input().rstrip().split() n = int(first_multiple_input[0]) m = int(first_multiple_input[1]) edges = [] for _ in range(m): edges.append(list(map(int, input().rstrip().split()))) s = int(input().strip()) result = bfs(n, m, edges, s) fptr.write(' '.join(map(str, result))) fptr.write('\n') fptr.close()
Seems like cookies are disabled on this browser, please enable them to open this website
Breadth First Search: Shortest Reach
You are viewing a single comment's thread. Return to all comments →