Algorithms and Data Structures

Depth First Search (DFS) Algorithm

Imagine that you are controlling a robot that is situated at some location in 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. The DFS algorithm allows you to do exactly that by first starting from a certain vertex, then exploring a certain path up until there are no more vertices on that path, then moving back to the previous nodes and exploring a certain path from there.
Video preview
Video by Reducible - Depth First Search (DFS) Explained: Algorithm, Examples, and Code
A great way of thinking about the DFS algorithm is the idea of a robot that starts exploring a graph and can only see the neighbors of the current node and all the nodes that it has already been to (so the robot keeps track of the whole path). This is a recursive process where on each iteration, the robot has to move to some new vertex that hasn’t been explored before and repeat that process until there are no vertices on that path. Keeping in mind the analogy of a small robot exploring the graph helps a lot in the implementation.
The implementation of the DFS algorithm can be done using a recursive algorithm where we keep track of the current vertex (which we will mark as v) and all the vertices that we have visited so far (which we will mark as used):
import sys

sys.setrecursionlimit(10 ** 6)          # Increase the recursion limit so that DFS can execute correctly

n, e = map(int, input().split())        # n: vertices, e: edges
g = [[] for _ in range(n)]              # graph - adjacency list
used = [False] * n                      # used vertices (visited)

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)


def dfs(v):                             # depth-first search
    used[v] = True                      # mark vertex as visited
    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
            dfs(to)                     # call dfs on that vertex


start = int(input())                    # start vertex
dfs(start)                              # call dfs on start vertex
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 mark it as used[v] = True, meaning that it is visited now and then move on to all the neighbors of the current vertex v.
Notice how the recursion acts the role of exploring the path and then going back to the previous location to continue exploring all the neighbors of the previous vertex. When we backtrack from the recursion, we basically move to the previous vertex.
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
  1. v = 3used = [False, False, False, True]
  1. explore all the neighbors of 3 ⇒ [2]
  1. v = 2used = [False, False, True, True]
  1. explore all the neighbors of 2 ⇒ [0, 1]
  1. v = 0used = [True, False, True, True]
  1. explore all the neighbors of 0 ⇒ [1, 2]
  1. v = 1used = [True, True, True, True]
  1. explore all the neighbors of 1 ⇒ [0, 2] ⇒ All are visited
  1. backtrack from 1
  1. backtrack from 0
  1. backtrack from 2
  1. backtrack from 3 → finish the DFS
  1. 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
  1. v = 0used = [True, False, False, False, False]
  1. explore all the neighbors of 0 ⇒ [1, 2]
  1. v = 1used = [True, True, False, False, False]
  1. explore all the neighbors of 1 ⇒ [0, 2]
  1. v = 2used = [True, True, True, False, False]
  1. explore all the neighbors of 2 ⇒ [0, 1] ⇒ All are visited
  1. backtrack from 2
  1. backtrack from 1
  1. backtrack from 0 → Finish the DFS
  1. Done
    1. Notice how nodes 3 and 4 were never visited.
      They were not connected to the initial node 0.
n = 10, e = 11 (example from the video)
The input a, b pairs are the following: [(0, 1), (0, 2), (1, 2), (1, 4), (1, 3), (3, 5), (6, 5), (5, 8), (5, 7), (7, 8), (8, 9)]
The starting vertex is 0
  1. v = 0used = [T, F, F, F, F, F, F, F, F, F] ⇒ explore [1, 2]
  1. v = 1used = [T, T, F, F, F, F, F, F, F, F] ⇒ explore [0, 2, 3, 4]
  1. v = 2used = [T, T, T, F, F, F, F, F, F, F] ⇒ explore [0, 1]
  1. Backtrack from 2
  1. v = 1used = [T, T, T, F, F, F, F, F, F, F] ⇒ explore [x, x, 3, 4]
  1. v = 3used = [T, T, T, T, F, F, F, F, F, F] ⇒ explore [1, 5]
  1. v = 5used = [T, T, T, T, F, T, F, F, F, F] ⇒ explore [3, 6, 7, 8]
  1. v = 6used = [T, T, T, T, F, T, T, F, F, F] ⇒ explore [5]
  1. Backtrack from 6
  1. v = 7used = [T, T, T, T, F, T, T, T, F, F] ⇒ explore [5, 8]
  1. v = 8used = [T, T, T, T, F, T, T, T, T, F] ⇒ explore [5, 7, 9]
  1. v = 9used = [T, T, T, T, F, T, T, T, T, T] ⇒ explore [8]
  1. Backtrack from 8
  1. Backtrack from 7
  1. Backtrack from 6
  1. Backtrack from 5
  1. Backtrack from 3
  1. v = 1used = [T, T, T, T, F, T, T, T, T, T] ⇒ explore [x, x, x, 4]
  1. v = 4used = [T, T, T, T, T, T, T, T, T, T] ⇒ explore [1]
  1. Backtrack from 4
  1. Backtrack from 1
  1. Backtrack from 0
  1. Done
 

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: 2.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue