Problem

1/6

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

Theory Click to read/hide

اتساع البحث الأول ( BFS )
BFS & nbsp؛ (بحث العرض أولاً ، بحث العرض أولاً ) - طريقة مسح الرسم البياني ، تُستخدم غالبًا في كل من الخوارزميات البسيطة والمتقدمة. يعمل بحث Breadth-First عن طريق التنقل خلال المستويات الفردية للرسم البياني ، بدءًا من العقدة المصدر والانتقال تدريجياً بعيدًا عنها. يظهر هذا بوضوح في الرسوم المتحركة.
لكتابة أبسط BFS & nbsp؛ ، يجب أن تكون قادرًا على العمل بهيكل بيانات يسمح لك بأخذها من البداية & nbsp ؛ ووضعها حتى النهاية ، وأيضًا أن تكون قادرًا على التخزين الرسم البياني في شكل قائمة مجاورة (أي مع قائمة انتظار).
نبسب ؛
وصف رسمي للخوارزمية
1) ضع رقم الرأس الذي يبدأ منه البحث في قائمة الانتظار الفارغة في البداية.
2) قم باستخراج قمة الرأس U من بداية قائمة الانتظار وتمييزها على أنها مستخدمة في مصفوفة منفصلة.
3) في نهاية قائمة الانتظار ، أضف جميع الرؤوس & nbsp ؛ التي يمكننا الوصول إليها & nbsp ؛ باستخدام الحافة من الرأس U ، & nbsp ؛ والتي لم يتم تصنيفها بعد.
4) إذا كانت قائمة الانتظار فارغة ، فهذا يعني أنه تم فحص جميع عقد الرسم البياني المتصل ، وإلا فارجع إلى الخطوة 2.
نبسب ؛
التعقيد
نظرًا لأن الخوارزمية تزور جميع عُقد الرسم البياني في أسوأ الحالات ، عند تخزين الرسم البياني كقوائم مجاورة ، & nbsp ؛ التعقيد الزمني للخوارزمية هو O (| V | + | E |) ، حيث V هي مجموعة رؤوس الرسم البياني ، و E هي مجموعة الحواف. & nbsp ؛ بمعنى آخر ، تعمل الخوارزمية في أسوأ حالة لرقم عدد الأضلاع + عدد الرؤوس .
نبسب ؛

Problem

ترتبط بعض القرى ببعضها البعض بواسطة طرق يمكن تمثيلها كرسم بياني & nbsp؛ غير موجه. رؤوس هذا الرسم البياني عبارة عن قرى ، والحواف عبارة عن طرق بين القرى (قد يحتوي الرسم البياني على دورات). & nbsp؛ من المعروف أنه في القرية & nbsp؛ S an artel Pedlars . & nbsp؛ كل صباح ، لبيع الخردوات الصغيرة الخاصة بهم ، يذهب الباعة المتجولون إلى القرى التي & nbsp ؛ لم تزرها بعد ، وهناك طريق من الطريق الحالي. دائمًا ما يتم تقسيم أرتل الباعة المتجولين إلى مجموعات حتى يتمكنوا من التجول في جميع القرى التي توجد بها طرق من القرية الحالية في يوم واحد.
كم يوما سيزور الباعة المتجولون كل القرى؟ اكتب وظيفة BFS والتي ستعيد الإجابة على المهمة.

نبسب ؛
إدخال
يحتوي السطر الأول على 3 أعداد صحيحة n ، m ، s & nbsp؛ ( \ (1 & lt؛ = n & lt؛ = 10 ^ 5 \) ، \ (0 & lt؛ = m & lt؛ = 10 ^ 5 \) ، \ (1 & lt؛ = s & lt؛ = n \) ) - عدد القرى وعدد الطرق بينها وعدد القرية التي تتمركز فيها عصابة الباعة المتجولين. & nbsp ؛ في السطور التالية m تحتوي على رقمين لكل منهما u ، v ( \ (1 & lt؛ = u، v & lt؛ = n \) ) - عدد قريتين يوجد بينهما طريق. تتم فهرسة القرى بـ 1 .

بصمة
اطبع رقمًا واحدًا - كم عدد الأيام التي سيستغرقها الباعة المتجولون لزيارة جميع القرى.

نبسب ؛

أمثلة <الجسم>
# إدخال الإخراج
1 6 7 1
1 2
15
23
5 4
34
36
4 6 		4

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>
#include<queue>
#include<algorithm>
#include<cmath>

using namespace std;

vector<bool> used;   
// used[i] = true, если мы были в вершине i
vector<vector<int> > g;   // список смежности
vector<int> tm;     
// tm[i] - день, когда в деревню i 
// пришла артель коробейников
int n, m, s;

int bfs()
{                   
}

int main()
{
	cin >> n >> m >> s;
	s--;
	g.resize(n);
	tm.resize(n);
	used.assign(n, false);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cout << bfs();
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!