Алгоритм Depth First Search (DFS)

Представьте, что вы управляете роботом, который находится в некоторой вершине графа, где всего в графе n вершин и e рёбер. Вы хотите начать обход с одной вершины и постепенно пройти по всему графу, посетив все вершины, до которых можно добраться из начальной точки. Алгоритм DFS позволяет сделать это, начав с некоторой вершины, затем исследуя один путь до тех пор, пока там не останется непосещённых вершин, после чего робот «возвращается» к предыдущим узлам и начинает исследовать другие пути.

Удобно представлять работу алгоритма DFS как перемещение маленького робота по графу, который «видит» только соседей текущей вершины и помнит все уже посещённые вершины (фактически, весь пройденный путь). Работа алгоритма рекурсивна: на каждом шаге робот переходит в новую непосещённую вершину и продолжает процесс до тех пор, пока на текущем пути не останется непроверенных вершин. Аналогия с небольшим роботом, пробирающимся по графу, очень помогает при реализации алгоритма.

Реализовать DFS можно через рекурсивный алгоритм, где мы следим за текущей вершиной (обозначим её как v) и массивом уже посещённых вершин (обозначим его как used):

import sys

sys.setrecursionlimit(10 ** 6)          # Увеличиваем лимит рекурсии, чтобы DFS работал корректно

n, e = map(int, input().split())        # n: вершины, e: рёбра
g = [[] for _ in range(n)]              # граф – список смежности
used = [False] * n                      # посетили ли вершину

for _ in range(e):                      # читаем рёбра
    a, b = map(int, input().split())    # a -> b и b -> a
    g[a].append(b)
    g[b].append(a)


def dfs(v):                             # обходим в глубину
    used[v] = True                      # отмечаем вершину как посещённую
    print(v, end=' ')                   # выводим её
    for to in g[v]:                     # идём по всем соседям v
        if not used[to]:                # если сосед не посещён
            dfs(to)                     # вызываем dfs для него


start = int(input())                    # стартовая вершина
dfs(start)                              # запускаем DFS от стартовой вершины

В начале мы инициализируем граф и запускаем обход с вершины start. Изначально все элементы в used равны False. Когда мы посещаем вершину, мы ставим used[v] = True, что означает, что вершина теперь посещена, а затем переходим к соседям текущей вершины v.

Заметьте, что рекурсия играет роль «ухода» по пути вглубь, а затем возврата к предыдущей вершине, чтобы продолжить обход соседей уже оттуда. Когда мы «возвращаемся» из рекурсивного вызова, это означает переход обратно к предыдущей вершине.

Давайте посмотрим, как алгоритм работает на нескольких примерах:

Задача: Посчитать количество компонент связности в графе

Пусть дан неориентированный граф с v вершинами и e рёбрами. Нужно найти, сколько в нём компонент связности. Под «компонентой связности» понимается набор вершин, между которыми можно добраться из одной в другую.

Входные данные

Первая строка содержит два целых числа v (1 ≤ v ≤ 100 000) и e (1 ≤ e ≤ 100 000).

В следующих e строках записаны пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), обозначающие, что вершина v1 соединена с вершиной v2 и наоборот.

Выходные данные

Программа должна вывести количество компонент связности в графе.

Примеры