Модуль: Поиск в глубину. DFS


1. DFS: Начало (C++)

☰ Теория

Поиск в глубину DFS
Поиск в глубину (DFS) - это один из основных алгоритмов на графах. Алгоритм работает за O(N + M).
 
Алгоритм
Для начала мы запускаемся от вершины, рассматриваем детей этой вершины, и если мы никогда в них не заходили, то запускаем от них DFS.


Написать процедуру void dfs (int v), которая обходит в глубину неориентированный граф от начальной вершины S и выводит все вершины в порядке обхода, начиная с вершины S через пробел в одной строке.

В первой строчке заданы три числа N - количество вершин в графе, M - количество ребер, S - стартовая вершина. В следующих M строках подаются 2 переменные Ui и Vi, описание ребер графа. Все числа во входных данных не превышают 1000.

Вывести все вершины в порядке обхода алгоритмом DFS.

В приведенной программе, g[i][j] обозначает, что между вершинами i и j есть ребро, а в массиве used мы отмечаем заходили ли мы в эту вершину. 
Вставьте недостающие фрагменты кода
C++
Напишите программу ниже 
#include <iostream>
#include <vector>

using namespace std;

vector < vector < int > > g;
vector < bool > used;

void dfs(int v) 
{            
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m, s, u, v;

	cin >> n >> m >> s;

	g.resize(n);
	used.resize(n);

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		g[u - 1].push_back(v - 1);
		g[v - 1].push_back(u - 1);
	}

	dfs(s - 1);
	return 0;
}
     

time 1000 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!