Module: Cerca in profondità. DFS


Problem

1/12

DFS: Inizio (C++)

Theory Click to read/hide

DFS DFS
La prima ricerca in profondità (DFS) è uno dei principali algoritmi sui grafici. L'algoritmo viene eseguito in O(N + M).
 
Algoritmo
Per cominciare, partiamo dall'alto, consideriamo i figli di questo top, e se non li abbiamo mai inseriti, allora iniziamo DFS da loro.


Problem

Scrivi una procedura void dfs (int v) che attraversi la profondità di un grafo non orientato dal vertice iniziale S e generi tutti i vertici in ordine di attraversamento, partendo dal vertice S separati da uno spazio su una riga.

La prima riga contiene tre numeri N  - il numero di vertici nel grafico, M - il numero di spigoli, S - il punto iniziale vertice. Nelle seguenti righe M, 2 variabili Ui e Vi sono forniti , descrizione degli spigoli del grafo. Tutti i numeri inseriti non superano 1000.

Visualizza tutti i vertici in ordine di attraversamento tramite DFS.

Nel programma precedente, g[i][j] significa che c'è un bordo tra i vertici i e j, e in l'array usato contrassegniamo se abbiamo visitato questo picco. 

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!