Module: Pesquise em profundidade. DFS


Problem

1/12

DFS: Iniciando (C++)

Theory Click to read/hide

DFS DFS
A pesquisa em profundidade (DFS) é um dos principais algoritmos em gráficos. O algoritmo é executado em O(N + M).
 
Algoritmo
Para começar, começamos do topo, consideramos os filhos deste topo e, se nunca os inserimos, iniciamos o DFS a partir deles.


Problem

Escreva um procedimento void dfs (int v) que percorra a profundidade de um gráfico não direcionado a partir do vértice inicial S e mostre todos os vértices em ordem de passagem, começando no vértice S separados por um espaço em uma linha.

A primeira linha contém três números N  - o número de vértices no grafo, M - o número de arestas, S - o início vértice. Nas seguintes linhas M, 2 variáveis ​​Ui e Vi são fornecidos , descrição das arestas do gráfico. Todos os números na entrada não excedem 1000.

Gere todos os vértices na ordem de passagem por DFS.

No programa acima, g[i][j] significa que existe uma aresta entre os vértices i e j, e em o array used marcamos se visitamos este pico. 

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#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;
}

     

Program check result

To check the solution of the problem, you need to register or log in!