BFS Traversal

Practice this coding question on Coding Gurukul.

Problem statement

Given an undirected graph and a starting vertex s, print its Breadth-First Search (BFS) traversal. Use a queue. Mark a vertex visited when you add it to the queue. For each vertex, check its neighbors in increasing numeric order. Print vertices in the order they leave the queue. Visit each vertex once. Include only vertices reachable from s. Self-loops and repeated edges must not cause repeated visits. Print s even if it has no edges. Worked example From 0, visit neighbors 1 and 2 before visiting 3 through vertex 1. The order is 0 1 2 3. Vertex 4 is disconnected and is not printed.

Input format

First line: n m s. Next m lines: undirected edge endpoints u v.

Output format

Print the traversal order as space-separated vertex numbers.

Constraints

1 <= n <= 100000; 0 <= m <= 200000; 0 <= s,u,v < n.

Sample input

5 3 0
0 2
1 3
0 1

Sample output

0 1 2 3

Sign in to run or submit a solution in C++, Java or Python.