Module: 徹底的に検索します。 DFS


Problem

1/12

DFS: はじめに (C++)

Theory Click to read/hide

DFS DFS
深さ優先検索 (DFS) は、グラフに関する主要なアルゴリズムの 1 つです。アルゴリズムは O(N + M) で実行されます。
 
アルゴリズム
まず、トップから始めて、このトップの子を考えます。まだ入力していない場合は、それらから DFS を開始します。


Problem

開始頂点 S から無向グラフの深さを横断し、頂点から開始してすべての頂点を横断順序で出力するプロシージャ void dfs (int v) を記述します S はスペースで区切られた 1 行です。

最初の行には 3 つの数値 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!