Module: 深入搜索。数字文件系统


Problem

1/12

DFS：开始 (C++)

Theory Click to read/hide

DFS DFS
深度优先搜索 (DFS) 是图上的主要算法之一。该算法在 O(N + M) 中运行。
 
算法
首先，我们从顶部开始，考虑这个顶部的子项，如果我们从未输入过它们，那么我们从它们开始DFS。


Problem

编写一个程序void dfs (int v)从起始顶点S遍历无向图的深度，并按遍历顺序输出所有顶点，从顶点开始 S 在一行中以空格分隔。

第一行包含三个数字 N  - 图中的顶点数，M - 边数，S - 起点顶点。在接下来的 M 行中，2 个变量 Ui 和 Vi 提供了 ，图边的描述。输入的所有数字不超过 1000。

通过 DFS遍历的顺序输出所有顶点。

上述程序中， g[i][j]表示顶点i和j之间有一条边，在数组used我们标记我们是否访问过这个峰。 

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!