Задача: Дан неориентированный связный граф, не содержащий кратных ребер и петель, представленный списком смежности. Необходимо выполнить обход в глубину (DFS), начиная с заданной вершины.

Формат входных данных: В первой строке заданы два числа: n и m (1 ≤ n, m ≤ 100000) – количество вершин и количество рёбер соответственно. В следующих m строках заданы пары целых чисел v и u (1 ≤ u, v ≤ n), обозначающие ребро между вершинами v и u (граф неориентированный). Последняя строка содержит одно число s – номер стартовой вершины.

Формат выходных данных: В первой строке выведите порядок обхода вершин через пробел. Далее в n строках для каждой посещённой вершины выведите путь от стартовой вершины до неё.

Решение: Для решения задачи используется алгоритм DFS. Создаётся список used для отметки посещённых вершин, а также массив parent для восстановления пути от текущей вершины до стартовой.

Начальное условие:

used = [False] * n

parent = [-1] * n

Рекурсивная функция dfs посещает вершину, отмечает её как посещённую, добавляет её в список обхода, а затем для каждого непосещённого соседа обновляет массив parent и рекурсивно вызывает себя.

После завершения обхода, для восстановления пути от стартовой вершины до любой другой вершины, можно пройтись по массиву parent: