Module: BFS - پیاده روی عرض


Problem

1/6

BFS: شروع (C++)

Theory Click to read/hide

اولین جستجوی پهنا (BFS)
BFS (جستجوی عرض-اول، جستجوی عرض-اول) - یک روش پیمایش نمودار، که اغلب در الگوریتم های ساده و پیشرفته استفاده می شود. جستجوی Breadth-First با قدم گذاشتن در سطوح جداگانه نمودار، شروع از گره منبع و دور شدن تدریجی از آن کار می کند. این به وضوح در انیمیشن نشان داده شده است.
برای نوشتن ساده ترین BFS ، باید بتوانید با ساختار داده ای کار کنید که به شما امکان می دهد از ابتدا  بردارید و آن را تا آخر قرار دهید و همچنین بتوانید ذخیره کنید نمودار به شکل یک لیست مجاورت (یعنی با یک صف).
 
توضیحات رسمی الگوریتم
1) شماره رأسی را که جستجو از آن شروع می شود در صف اولیه خالی قرار دهید.
2) راس U را از ابتدای صف استخراج کرده و آن را به عنوان مورد استفاده در یک آرایه جداگانه علامت گذاری کنید.
3) در انتهای صف، تمام رئوس‌هایی را که می‌توانیم با استفاده از لبه راس U, به آنها برسیم و هنوز برچسب‌گذاری نشده‌اند، اضافه کنید.
4) اگر صف خالی باشد، تمام گره های گراف متصل شده اسکن شده اند، در غیر این صورت به مرحله 2 برگردید.
 
پیچیدگی
از آنجایی که الگوریتم در بدترین حالت از تمام گره های نمودار بازدید می کند، هنگام ذخیره نمودار به عنوان لیست های مجاورت، پیچیدگی زمانی الگوریتم O(|V| + |E|) است. ، که در آن V مجموعه ای از رئوس نمودار است و E مجموعه ای از یال ها است. به عبارت دیگر، الگوریتم در بدترین حالت برای عدد کار می کند. از یال ها + تعداد رئوس.

 

Problem

برخی از روستاها با جاده هایی به هم متصل می شوند که می توان آنها را به عنوان یک گراف جهت نشده نشان داد. رئوس این نمودار روستاها و لبه ها جاده های بین روستاها هستند (گراف ممکن است شامل چرخه باشد). مشخص است که در روستا S یک آرتل دستفروشان. دستفروشان هر روز صبح برای فروش مغازه خرطومی کوچک خود به روستاهایی می روند که هنوز به آنها سر نزده اند و از جاده فعلی به آنها راهی وجود دارد. دستفروشان همیشه به گروه‌هایی تقسیم می‌شوند تا بتوانند در یک روز تمام روستاهایی را که جاده‌ای از روستای کنونی دارند، بچرخند.
دستفروشان چند روز دیگر به همه روستاها سر می زنند؟ یک تابع BFS بنویسید که پاسخ را به کار برمی گرداند.

 
ورودی
خط اول شامل 3 عدد صحیح n، m، s (\(1 < = n <= 10^5\)، \(0 <= m <= 10^5\)، \(1 <= s <= n\)) - تعداد روستاها، تعداد جاده های بین آنها و تعداد روستایی که گروه دستفروشان در آن مستقر هستند.  ;در خطوط m< /code> زیر شامل 2 عدد u، v(\(1 < = u, v <= 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!