# Breadth First Search (BFS) Algorithm

Imagine that given a graph with

`n`

vertices and `e`

edges, you’d like to start from one vertex and gradually traverse the whole graph by visiting all the possible vertices reachable from the starting point. There are several ways of doing that, and one of the most popular approaches is Breadth-First-Search (BFS) algorithm. By its nature, BFS allows one to calculate the shortest path from the source vertex to all the other vertices in the graph, which makes it super useful in various applications.A great way of thinking about the BFS algorithm is the idea of burning the graph and watching how the fire expands. Imagine that each vertex needs to burn for 1 minute, after which the fire is propagated to its immediate neighbors, after which they burn for 1 minute as well, and the fire propagates to their neighbors, and so on.

So, you burn the starting vertex. Then the fire propagates to all its neighbors. After waiting for a minute, their neighbors start burning as well, then the fire catches their neighbors as well. This process continues until there are no vertices left. Having this mental image of the graph burning down helps a lot when implementing the BFS algorithm.

The implementation of the BFS algorithm can be done using a

`queue`

and a list of vertices that keeps track of the `used`

vertices (the vertices that are burning):```
from collections import deque
n, e = map(int, input().split()) # n: vertices, e: edges
g = [[] for _ in range(n)] # graph - adjacency list
for _ in range(e): # read edges
a, b = map(int, input().split()) # a -> b and b -> a
g[a].append(b)
g[b].append(a)
start = int(input()) # start vertex
used = [False] * n # used vertices (visited)
q = deque([start]) # queue of vertices
used[start] = True # mark start vertex as visited
while q: # while the queue is not empty
v = q.popleft() # get vertex from queue
print(v, end=' ') # print vertex
for to in g[v]: # for each vertex connected to v
if not used[to]: # if vertex is not visited
q.append(to) # add vertex to queue
used[to] = True # mark vertex as visited
```

Here we first initialize the graph and start the graph traversal from the

`start`

vertex. Initially, all the `used`

values are set to `Fasle`

. After visiting each vertex, we first add it to the queue and mark it as used. This simulates the “burning” of the graph. On each step, we add all the adjacent not used vertices of the current vertex `v`

in the graph to the queue and mark them as used.Let’s simulate the algorithm on several inputs:

## n = 4, e = 4

The input

`a, b`

pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 2)]The starting vertex is 3

`used = [False, False, False, True]`

,`q = [3]`

`v = 3`

,`q = []`

→ add all the neighbors that are not used to the queue

`used = [False, False, True, True]`

,`q = [2]`

`v = 2`

,`q = []`

→ add all the neighbors that are not used to the queue

`used = [True, True, True, True]`

,`q = [0, 1]`

`v = 0`

,`q = [1]`

→ add all the neighbors that are not used to the queue

`v = 1`

,`q = []`

→ add all the neighbors that are not used to the queue

- Done

## n = 5, e = 4

The input

`a, b`

pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 4)]The starting vertex is 0

`used = [True, False, False, False, False]`

,`q = [0]`

`v = 0`

,`q = []`

→ add all the neighbors that are not used to the queue

`used = [True, True, True, False, False]`

,`q = [1, 2]`

`v = 1`

,`q = [2]`

→ add all the neighbors that are not used to the queue

`v = 2`

,`q = []`

→ add all the neighbors that are not used to the queue

- Done

Notice how nodes 3 and 4 were never visited.

They were not connected to the initial node 0.

Challenge: Count the Number of Connected Components in a Graph

Given an undirected graph with

`v`

vertices and `e`

edges, you are asked to calculate the number of connected components in the graph. A set of vertices is considered to be a connected component if one can travel between those vertices. Input

The first line of the input contains two integers

`v`

(1 ≤ v ≤ 100 000) and `e`

(1 ≤ e ≤ 100 000).The following

`e`

lines contain pairs of integers `v1`

, `v2`

(1 ≤ v1, v2 ≤ v) which means that the vertex `v1`

is connected to the vertex `v2`

and vice versa. Output

The program should print the number of the connected components in the graph.

Examples

Input | Output |

7 6
1 2
2 3
1 3
4 5
5 6
4 6 | 3 |

2 1
1 2 | 1 |

2 0 | 2 |

#### Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 1 MB