Problem

1/12

DFS: البداية (C ++)

Theory Click to read/hide

DFS & nbsp؛ DFS
يعد بحث العمق الأول ( DFS ) أحد الخوارزميات الرئيسية في الرسوم البيانية. تعمل الخوارزمية في O (N + M) .
نبسب ؛
الخوارزمية بادئ ذي بدء ، نبدأ من الأعلى ، ونفكر في أطفال هذا الجزء العلوي ، وإذا لم نقم بإدخالهم مطلقًا ، فسنبدأ منهم DFS .


Problem

اكتب إجراء باطل dfs (int v) يمر بعمق رسم بياني غير موجه من قمة البداية S ويخرج جميع القمم بترتيب اجتياز ، بدءًا من الرأس S مفصولة بمسافة في سطر واحد.

يحتوي السطر الأول على ثلاثة أرقام N & nbsp؛ - عدد الرؤوس في الرسم البياني ، M - عدد الحواف ، S - البداية قمة الرأس. في سطور M التالية ، متغيرين U i و V i يتم توفيرها ، وصف حواف الرسم البياني. جميع الأرقام في الإدخال لا تتجاوز 1000.

إخراج جميع القمم بترتيب الاجتياز بواسطة & nbsp؛ DFS .

في البرنامج أعلاه ، تعني & nbsp؛ g [i] [j] أن هناك حافة بين القمم i و j ، وفي المصفوفة used نحدد ما إذا كنا قد زرنا هذه الذروة. & nbsp؛

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!