Module: Search in depth. DFS


Problem

1/12

DFS: Beginning (C++)

Theory Click to read/hide

DFS DFS
Depth first search (DFS) is one of the main algorithms on graphs. The algorithm runs in O(N + M).
 
Algorithm
To begin with, we start from the top, consider the children of this top, and if we have never entered them, then we start DFS from them.


Problem

Write a procedure void dfs (int v) that traverses the depth of an undirected graph from the start vertex S and outputs all vertices in traversal order, starting at vertex S separated by a space on one line.

The first line contains three numbers N  - the number of vertices in the graph, M - the number of edges, S - the starting vertex. In the following M lines, 2 variables Ui and Vi are supplied , description of graph edges. All numbers in the input do not exceed 1000.

Output all vertices in order of traversal by DFS.

In the above program, g[i][j] means that there is an edge between the vertices i and j, and in the array used we mark whether we have visited this peak. 

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!