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.

Video preview — Video by Reducible - Breadth First Search (BFS): Visualized and Explained

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

Challenge: Count the Number of Connected Components in a Graph

Input

Output

Examples

Constraints

To check your solution you need to sign in

Sign in to continue